HDU 5305 Friends(dfs)

题意:

$给定N\le 8,M\le N(N-1)/2的图$
$现要给边染色,使得每个点的边一半是白,一半是黑$
$求满足条件的方法数$

分析:

$如果枚举边的颜色的话,边数有28,复杂度是2^{28}会T$
$考虑到一半一半,所以所有点的度数必须是偶数(一个剪枝),边数是24$
$但是没有根本的改变结果,考虑对每个点的所有边进行染色,由于边确定了$
$下一个节点的一些边的颜色会被确定,会使得枚举的边变少,达不到24,现在就很快了$
$至此问题解决,时间复杂度O(1s内可过)$

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
//
// Created by TaoSama on 2016-03-17
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, ans;
int g[10][10], deg[10];
vector<vector<int> > get(int u, int w) {
vector<vector<int> > ret;
vector<int> vec;
if(w == 0) ret.push_back(vec);
if(w == 1) {
for(int i = 1; i <= n; ++i) {
if(g[u][i] != 1 || i == u) continue;
vec.push_back(i);
ret.push_back(vec);
vec.pop_back();
}
}
if(w == 2) {
for(int i = 1; i <= n; ++i) {
if(g[u][i] != 1 || i == u) continue;
vec.push_back(i);
for(int j = i + 1; j <= n; ++j) {
if(g[u][j] != 1 || j == u) continue;
vec.push_back(j);
ret.push_back(vec);
vec.pop_back();
}
vec.pop_back();
}
}
if(w == 3) {
for(int i = 1; i <= n; ++i) {
if(g[u][i] != 1 || i == u) continue;
vec.push_back(i);
for(int j = i + 1; j <= n; ++j) {
if(g[u][j] != 1 || j == u) continue;
vec.push_back(j);
for(int k = j + 1; k <= n; ++k) {
if(g[u][k] != 1 || k == u) continue;
vec.push_back(k);
ret.push_back(vec);
vec.pop_back();
}
vec.pop_back();
}
vec.pop_back();
}
}
return ret;
}
void dfs(int u) {
if(u == n + 1) {
++ans;
return;
}
int w = 0, b = 0;
for(int v = 1; v <= n; ++v) {
if(g[u][v] == 2) ++w;
if(g[u][v] == 3) ++b;
}
if(w > deg[u] / 2 || b > deg[u] / 2) return;
vector<vector<int> > white = get(u, deg[u] / 2 - w);
for(auto& vec : white) {
int tmp[10][10];
memcpy(tmp, g, sizeof g);
for(int wh : vec) g[u][wh] = g[wh][u] = 2;
for(int v = 1; v <= n; ++v) if(g[u][v] == 1) g[u][v] = g[v][u] = 3;
dfs(u + 1);
memcpy(g, tmp, sizeof tmp);
}
}
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
int t; scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
if(!m) {puts("1"); continue;}
memset(g, 0, sizeof g);
memset(deg, 0, sizeof deg);
for(int i = 1; i <= m; ++i) {
int u, v; scanf("%d%d", &u, &v);
g[u][v] = g[v][u] = 1;
++deg[u]; ++deg[v];
}
bool ok = true;
for(int i = 1; i <= n; ++i)
if(deg[i] & 1) ok = false;
if(!ok) {puts("0"); continue;}
ans = 0;
dfs(1);
printf("%d\n", ans);
}
return 0;
}


1. 除非注明,本博文即为原创,转载请注明链接地址
2. 本博文只代表博主当时的观点或结论,请不要恶意攻击
3. 如果本文帮到了您,不妨点一下 下面分享到 按钮,让更多的人看到