难以置信ramsey(ramsey定理)

算法合集系列文章之~拉姆齐（Ramsey）定理，5分钟快速理解~

 

拉姆齐Ramsey定理是一个稍微难于理解的定理，该定理又称拉姆齐二染色定理，是要解决这样的问题：要找这样一个最小的数 R(k,l)=n，使得 n 个人中必定有 k 个人相识或 l 个人互不相识比如本题中的R(3,3) = 6，有3个人认识或者3个人互不认识，最小的数是6个人。

6个人中必有3个人相互认识或者相互不认识。证明并不难，采用二染色方法比较直观的来看看吧。对于一个有向图G，有6个节点，边只有蓝色或者红色。

假定G是一个完全图，我们选取一个节点1，它有5条边与其他节点相连。如下图：

根据我们之前学过的鸽巢原理，5条边中至少有3条是同一种颜色。

对于节点3、4、5，他们之间有3条边。

注意这3条边如果有一条是红色，比如3-5。

那么1-3-5就构成了一个红色三角形。如果这3条边全是蓝色，那么3-4-5构成了一个蓝色三角形。

于是拉姆齐定理就这样被证明了不管这6个节点之间的边是什么颜色（蓝色表示认识，红色表示不认识），都会不可避免的构成一个三边是同色的三角形而这个三角形正好表示有3个人认识或者3个人互不认识好了，原理大概就讲到这里，希望你能有所收获。

来看题~Problem DescriptionIt is well known that small groups are not conducive of the development of a team. Therefore, there shouldn’t be any small groups in a good team.

通常来说，公司里面搞拉帮结派的小团伙对于团队的发展是不利的因此，应该尽可能少的避免这些小团伙In a team with n members,if there are three or more members are not friends with each other or there are three or more members who are friends with each other. The team meeting the above conditions can be called a bad team.Otherwise,the team is a good team.。

一个团队里面有 n 个成员，如果有3个人及以上的人互为朋友或者都不是朋友关系，那么我们就说这个团队是bad teamA company is going to make an assessment of each team in this company. We have known the team with n members and all the friend relationship among these n individuals. Please judge whether it is a good team.。

公司现在准备做一个评估，看公司里面所有团队的好坏情况请通过上面的逻辑来评价团队的是否是一个好的teamInputThe first line of the input gives the number of test cases T; T test cases follow.（T<=15）。

The first line od each case should contain one integers n, representing the number of people of the team.(n≤3000)

第一行是用例数T接下来是团队人数nThen there are n-1 rows. The ith row should contain n-i numbers, in which number aij represents the relationship between member i and member j+i. 0 means these two individuals are not friends. 1 means these two individuals are friends.

接下来n-1行，第i行包含n-i个数字，对于数字aij，表示第i个人和第i+j个人的关系，0表示不是朋友，1表示朋友OutputPlease output ”Great Team!” if this team is a good team, otherwise please output “Bad Team!”.。

如果评估是好的团队，输出Great Team!，否则输出Bad Team!Sample Input1 4 1 1 0 0 0 1Sample OutputGreat Team!题目解析：拉姆齐定理的典型应用。

如果大于6个人，则肯定是不好的团队，根据拉姆齐定理： 6 个人中至少存在3人相互认识或者相互不认识源代码：G++#includeusingnamespacestd;bool

 G[6][6];intmain(){int T;scanf("%d", &T);//用例次数while ( T-- )    {int n;scanf("%d", &n);//输入n-1行for ( 

int i = 1; i <= n; i++ )        {for ( int j = i + 1; j <= n; j++ )            {int e;scanf("%d", &e);

//设置关系if ( n <= 6 )                    G[j][i] = G[i][j] = e;            }        }//如果只有1、2个人，则肯定是好团队（要么认识、要么不认识）

if (n < 3)        {printf("Great Team!\n");continue;        }//如果大于6个人，则肯定是不好的团队，根据拉姆齐定理： 6 个人中至少存在3人相互认识或者相互不认识。

if (n >= 6)        {printf("Bad Team!\n");continue;        }//暴力搜索（量级非常小）bool flag = false;for ( int a = 

1; a <= n; a++ )for ( int b = a + 1; b <= n; b++ )for ( int c = b + 1; c <= n; c++ )if ( (G[a][b] && G[a][c] && G[b][c]) ||

                            (!G[a][b] && !G[a][c] && !G[b][c]) )                        flag = true;if

 ( flag )  printf("Bad Team!\n");elseprintf("Great Team!\n");    }return0;}

温馨提示如果你喜欢本文，请分享到朋友圈，想要获得更多信息，请关注ACM算法日常。

点赞的时候，请宠溺一点

免责声明：本站所有信息均搜集自互联网，并不代表本站观点，本站不对其真实合法性负责。如有信息侵犯了您的权益，请告知，本站将立刻处理。联系QQ：1640731186