【GPLT】 图着色问题(c++)
题目如下:
这道题就是奇葩,多少有点低质量,这题不难,知识点就是邻接矩阵,但有以下奇葩点
1.颜色的编号是1-v 不是1-k,这点卡了我一会;
2.颜色涂色可以多于3,也可以少于3(这其实正常,但如果不在意这个25分就只能得6分)
明白这两点,再明白邻接矩阵和map就可以做出了
代码如下(就算没有注释基本没有看不懂的吧,基本就是暴力做)
1 #include//万能头文件 2 using namespace std; 3 typedef long long ll;//偷懒用 4 int a[506][506];//邻接矩阵,用来储存边 5 int f[506];//点的颜色编号储存 6 map<int,int>mp; 7 int main() 8 { 9 int n,m,k; 10 cin>>n>>m>>k; 11 int x1,x2; 12 for(int i=1;i<=m;i++) 13 { 14 cin>>x1>>x2; 15 a[x1][x2]=a[x2][x1]=1;//注意是两个,要是只有一个,后面的优化就要改变 16 } 17 int ff; 18 cin>>ff; 19 for(int j=1;j<=ff;j++) 20 { 21 int x; 22 for(int i=1;i<=n;i++) 23 { 24 cin>>x; 25 mp[x]++; 26 f[i]=x; 27 } 28 if(mp.size()!=k)//不要写>k这点卡了我一会 29 { 30 cout<<"No"<<endl; 31 goto kf;//无条件跳转,kf在46行 32 } 33 for(int i=1;i<=n;i++) 34 for(int j=i+1;j<=n;j++)//j=i+1 就是上面说的优化,这样可以减少不少计算 35 { 36 if(a[i][j]) 37 { 38 if(f[i]==f[j]) 39 { 40 cout<<"No"<<endl; 41 goto kf; 42 } 43 } 44 } 45 cout<<"Yes"<<endl; 46 kf:mp.clear(); 47 } 48 return 0; 49 }