图着色问题是一个著名的 NP 完全问题. 给定无向图 G=(V,E), 问可否用 K 种颜色为 V 中的每一个顶点分配一种颜色, 使得不会有两个相邻顶点具有同一种颜色?
但本题并不是要你解决这个着色问题, 而是对给定的一种颜色分配, 请你判断这是否是图着色问题的一个解.
输入格式:
输入在第一行给出 3 个整数 V(0<V≤500),E(≥0) 和 K(0<K≤V), 分别是无向图的顶点数, 边数, 以及颜色数. 顶点和颜色都从 1 到 V 编号. 随后 E 行, 每行给出一条边的两个端点的编号. 在图的信息给出之后, 给出了一个正整数 N(≤20), 是待检查的颜色分配方案的个数. 随后 N 行, 每行顺次给出 V 个顶点的颜色 (第 i 个数字表示第 i 个顶点的颜色), 数字间以空格分隔. 题目保证给定的无向图是合法的 (即不存在自回路和重边).
输出格式:
对每种颜色分配方案, 如果是图着色问题的一个解则输出 Yes, 否则输出 No, 每句占一行.
输入样例:
- 6 8 3
- 2 1
- 1 3
- 4 6
- 2 5
- 2 4
- 5 4
- 5 6
- 3 6
- 4
- 1 2 3 3 1 2
- 4 5 6 6 4 5
- 1 2 3 4 5 6
- 2 3 4 2 3 4
输出样例:
- Yes Yes No No
- #include<iostream>
- #include<string>
- #include<vector>
- #include<set>
- using namespace std;
- vector<vector<int>>G(501);
- int color[501] = { 0 };
- bool check(int V)
- {
- for (int i = 1; i <= V; i++)
- for (int j = 0; j <G[i].size(); j++)
- if (color[i] == color[G[i][j]])
- return false;
- return true;
- }
- int main()
- {
- int V, E, K, N;
- cin>> V>> E>> K;
- for (int i = 0; i <E; i++)
- {
- int start, end;
- cin>> start>> end;
- G[start].push_back(end);
- G[end].push_back(start);
- }
- cin>> N;
- for (int i = 0; i <N; i++)
- {
- set<int>color_kind;
- for (int j = 1; j <=V; j++)
- {
- cin>> color[j];
- color_kind.insert(color[j]);
- }
- if (check(V) && color_kind.size() == K)
- cout << "Yes" << endl;
- else
- cout << "No" << endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3388805.html