这是一篇最后编辑于 8 年前 的文章，其内容可能与目前实际情况差异较大，请注意甄别
题目
{% fold 点击显/隐题目 %}
Description 花老师有一个农场，农场的花一共有 4 种颜色， 花老师不喜欢老旧的东西，所以，她希望每天种花的方案都不一样。特别地，她也觉得两种一样颜色的花种在相邻的位置会很无聊。现在，她想知道，一共有多少种花的方案。这里要注意的是，农场的种花的位置是不规则的。因此我们给出一对一对的相邻的位置的关系。
第一行两个数 N 和 M，表示种花的位置的个数和相邻的位置的对数 接下来 M 行，每行一组数 A， B 表示 A， B 相邻
一个数表示染色方法数
题解
直接暴力跑就行
枚举所有的情况(使用递归),判断能否涂上特定的颜色,如果能成功枚举到终点就计数
不需要想太复杂
代码
{% fold 点击显/隐代码 %}```cpp 种花 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
//
#define debug
#include
///
#include
#include
#include
using namespace std;
const int maxn = 15;
const int maxm = 55;
bool Edge[maxn][maxn];
int color[maxn];
int n, m;
int sum;
bool judge(int t, int c) {
for (int i = 1; i <= n; i++) {
if (Edge[t][i]) { //相邻
if (color[i] == c) //有重复的颜色
return false;
}
}
return true;
}
//给t涂上c
void dfs(int t, int c, int deep) {
if (!judge(t, c))
return;
// for (int i = 0; i < deep; i++)
// cout << "\t";
// cout << "fill " << t << " in color " << c << endl;
color[t] = c;
if (t < n)
for (int k = 1; k <= 4; k++)
dfs(t + 1, k, deep + 1);
else
sum++;
color[t] = 0;
}
//从 s 开始给连通分量内的点涂色
int begin(int s) {
sum = 0;
for (int k = 1; k <= 4; k++) {
dfs(s, k, 0);
}
//cout << s << " " << sum << endl;
return sum;
}
int main() {
#ifdef debug
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int START = clock();
#endif
cin.tie(0);
cin.sync_with_stdio(false);
while (cin >> n >> m) {
memset(Edge, false, sizeof(Edge));
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
Edge[a][b] = Edge[b][a] = true;
}
int ans = begin(1);
/*
for (int i = 2; i <= n; i++) {
if (color[i] == 0) {
ans *= begin(i);
}
}
*/
cout << ans << endl;
}
#ifdef debug
printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;
}
{% endfold %}