网站建设俄语,微信如何修改wordpress,做平面设计的一般浏览什么网站,wordpress图像存储7-38 图着色问题 (25 分)图着色问题是一个著名的NP完全问题。给定无向图G(V,E)#xff0c;问可否用K种颜色为V中的每一个顶点分配一种颜色#xff0c;使得不会有两个相邻顶点具有同一种颜色#xff1f;但本题并不是要你解决这个着色问题#xff0c;而是对给定的一种颜色分配…7-38 图着色问题 (25 分)图着色问题是一个著名的NP完全问题。给定无向图G(V,E)问可否用K种颜色为V中的每一个顶点分配一种颜色使得不会有两个相邻顶点具有同一种颜色但本题并不是要你解决这个着色问题而是对给定的一种颜色分配请你判断这是否是图着色问题的一个解。输入格式输入在第一行给出3个整数V(0输出格式对每种颜色分配方案如果是图着色问题的一个解则输出Yes否则输出No每句占一行。输入样例6 8 32 11 34 62 52 45 45 63 641 2 3 3 1 24 5 6 6 4 51 2 3 4 5 62 3 4 2 3 4输出样例YesYesNoNo一个简单的遍历图的问题检查有连线的边颜色是否相同判断使用颜色的数目是否等于k必须要等于k大于小于都不行划重点。其他地方就没有难度了。#include#include#include#includeusing namespace std;#define maxn 505int map[maxn][maxn],judge[maxn][maxn];int color[maxn],tong[maxn];int n,m,k;int cmp(int a,int b){return ab;}void init(){for(int i 1; i n; i )for(int j 1; j n; j )map[i][j] maxn;}int main(){scanf(%d%d%d,n,m,k);init();for(int i 0; i m; i ){int x,y;scanf(%d %d,x,y);map[x][y] map[y][x] 1;}int t;scanf(%d,t);while(t--){int flag 0;memset(tong,sizeof(tong));for(int i 1; i n; i ){scanf(%d,color[i]);int temp color[i];tong[temp];}sort(tong,tong501,cmp);for(int i 0; i maxn; i ){if(tong[i])flag;elsebreak;}int index 0;if(flagk||flagprintf(Non);else if(!m)printf(Yesn);else{for(int i 1; i n; i ){for(int j i 1; j n; j ){if(map[i][j]!maxncolor[i]!color[j])index ;else if(map[i][j]maxn)continue;else if(map[i][j]!maxncolor[i]color[j]){index -1;break;}}if(index -1)break;}if(index m)printf(Yesn);elseprintf(Non);}}}总结以上是编程之家为你收集整理的数据结构-图着色问题全部内容希望文章能够帮你解决数据结构-图着色问题所遇到的程序开发问题。如果觉得编程之家网站内容还不错欢迎将编程之家网站推荐给程序员好友。本图文内容来源于网友网络收集整理提供作为学习参考使用版权属于原作者。小编个人微信号 jb51ccc喜欢与人分享编程技术与工作经验欢迎加入编程之家官方交流群
