大家好，欢迎来到IT知识分享网。
拉姆齐(Ramsey)定理是要解决以下的问题：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识
我们所知道的结论是这样的
6 个人中至少存在3人相互认识或者相互不认识。
该定理等价于证明这6个顶点的完全图的边，用红、蓝二色任意着色，必然至少存在一个红色边三角形，或蓝色边三角形
HDU6152
给出 n 个人之间的关系，如果其中有三个人互相认识或者互相不认识，则输出 Bad Team! ，否则输出 Great Team!
当人数大于等于 6 时其结果一定是 Bad Team!
而对于 n < 6 的情况，实际上需要求图的最大团点的个数是否大于 3
1 #include<cstdio> 2 #include<cstring> 3 int n; 4 int a[10][10]; 5 int main() 6 { 7 int T,t; 8 scanf("%d",&T); 9 while(T--) 10 { 11 scanf("%d",&n); 12 memset(a,0,sizeof(a)); 13 for(int i=1;i<n;i++) 14 for(int j=i+1;j<=n;j++) 15 { 16 scanf("%d",&t); 17 if(t&&n<6) a[i][j]=a[j][i]=1; 18 } 19 if(n>=6) 20 { 21 puts("Bad Team!"); 22 continue; 23 } 24 int f=0; 25 for(int i=1;i<=n;i++) 26 for(int j=i+1;j<=n;j++) 27 for(int k=j+1;k<=n;k++) 28 if(a[i][j]&&a[i][k]&&a[j][k]) 29 { 30 f=1; 31 break; 32 } 33 if(f) puts("Bad Team!"); 34 else puts("Great Team!"); 35 } 36 return 0; 37 }
转载于:https://www.cnblogs.com/aininot260/p/9584219.html
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/156874.html
