图论&数学：拉姆齐（Ramsey）定理

拉姆齐(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 }