L2-023 图着色问题 (25 分)
图着色问题是一个著名的 NP 完全问题. 给定无向图,, 问可否用 K 种颜色为 V 中的每一个顶点分配一种颜色, 使得不会有两个相邻顶点具有同一种颜色?
但本题并不是要你解决这个着色问题, 而是对给定的一种颜色分配, 请你判断这是否是图着色问题的一个解.
输入格式:
输入在第一行给出 3 个整数 V(0),E(≥) 和 K(0), 分别是无向图的顶点数, 边数, 以及颜色数. 顶点和颜色都从 1 到 V 编号. 随后 E 行, 每行给出一条边的两个端点的编号. 在图的信息给出之后, 给出了一个正整数 N(≤), 是待检查的颜色分配方案的个数. 随后 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
这题就是建个图, 然后跑一下相连的节点颜色不同, 还要判断颜色种类数必须为 K, 不能多也不能少.
代码:
- //2-3
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=1e6+10;
- typedef long long ll;
- struct node{
- int to,nex;
- }edge[2*maxn];
- int cnt;
- int head[2*maxn];
- int qw[2*maxn];
- void add(int u,int v)
- {
- edge[cnt].to=v;
- edge[cnt].nex=head[u];
- head[u]=cnt++;
- }
- int main()
- {
- int n,m,x;
- cin>>n>>m>>x;
- for(int i=1;i<=m;i++){
- int a,b;
- cin>>a>>b;
- add(a,b);
- add(b,a);
- }
- int q;
- cin>>q;
- while(q--){
- set<int> st;
- for(int i=1;i<=n;i++){
- cin>>qw[i];
- st.insert(qw[i]);
- }
- int flag=0;
- if(st.size()!=x) flag=1;
- for(int i=1;i<=n;i++){
- for(int j=head[i];j!=0;j=edge[j].nex){
- if(qw[edge[j].to]==qw[i]){
- flag=1;break;
- }
- }
- }
- if(!flag) cout<<"Yes"<<endl;
- else cout<<"No"<<endl;
- }
- }
OK, 关机, 准备上床瘫, 早睡, 明天天梯赛.
模拟赛的时候, 熬夜到 4 点, 打比赛的时候整个人都要死了, 题目没看清楚的, 写捞的, 错了好多, 罪过罪过.
虽然我是最菜的, 但是不能因为睡觉让我更菜, 到时候怕是要被队友们祭天了.
再见, 水完了.
来源: http://www.bubuko.com/infodetail-3004622.html