题目链接: https://www.luogu.com.cn/problem/P2819
题目大意: 求图的 m 着色方案数.
解题思路: 用搜索枚举没一个点的颜色, 如果 n 个点都染色且不冲突, 则方案数 + 1.
实现代码如下:
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 110;
- vector<int> g[maxn];
- int n, k, m, color[maxn], ans;
- void dfs(int u) {
- if (u> n) {
- ans ++;
- return;
- }
- int sz = g[u].size();
- for (int c = 1; c <= m; c ++) {
- bool flag = true;
- for (int i = 0; i <sz; i ++) {
- int v = g[u][i];
- if (color[v] == c) {
- flag = false;
- break;
- }
- }
- if (flag) {
- color[u] = c;
- dfs(u+1);
- color[u] = 0;
- }
- }
- }
- int main() {
- cin>> n>> k>> m;
- while (k --) {
- int a, b;
- cin>> a>> b;
- g[a].push_back(b);
- g[b].push_back(a);
- }
- dfs(1);
- cout << ans << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3396012.html