【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 }

相关