首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >朋友圈(拉姆齐定理)- HDU 6152

朋友圈(拉姆齐定理)- HDU 6152

作者头像
ACM算法日常
发布2018-12-13 17:57:29
1.1K0
发布2018-12-13 17:57:29
举报
文章被收录于专栏:ACM算法日常ACM算法日常

拉姆齐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 Description

It 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 team。

A 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.

公司现在准备做一个评估,看公司里面所有团队的好坏情况。请通过上面的逻辑来评价团队的是否是一个好的team。

Input

The 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

接下来是团队人数n

Then 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表示朋友。

Output

Please output ”Great Team!” if this team is a good team, otherwise please output “Bad Team!”.

如果评估是好的团队,输出Great Team!,否则输出Bad Team!

Sample Input

1 
4
1 1 
0 0 
0 1

Sample Output

Great Team!

题目解析:

拉姆齐定理的典型应用。如果大于6个人,则肯定是不好的团队,根据拉姆齐定理: 6 个人中至少存在3人相互认识或者相互不认识。

源代码:G++

#include <bits/stdc++.h>
using namespace std;

bool G[6][6];

int main()
{
    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");
        else printf("Great Team!\n");
    }
    return 0;
}
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-11-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 ACM算法日常 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档