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

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

本文分享自微信公众号 - ACM算法日常(acm-clan)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-11-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python专栏

200行代码,一行行教你自制微信机器人

1) 用一个windows客户端工具运营公众号,真的很局限。虽然工具的功能很强大,能自动添加好友,自动拉好友入群,关键字回复等等,但是有一个绕不开的点,它是一款...

62120
来自专栏机器之心

Diss所有深度生成模型,DeepMind说它们真的不知道到底不知道什么

深度学习在应用层面获得了巨大成功,这些实际应用一般都希望利用判别模型构建条件分布 p(y|x),其中 y 是标签、x 是特征。但这些判别模型无法处理从其他分布中...

11610
来自专栏GreenLeaves

TFS2018环境搭建一硬件要求

TFS可以安装在Windows Server和Windows PC操作系统中,但是TFS2018和2018只支持64位操作系统中,早期的版本没有操作系统的位数限...

41030
来自专栏苦逼的码农

一些常用的算法技巧总结

数组的下标是一个隐含的很有用的数组,特别是在统计一些数字,或者判断一些整型数是否出现过的时候。例如,给你一串字母,让你判断这些字母出现的次数时,我们就可以把这些...

21530
来自专栏我是攻城师

理解BitMap算法的原理

位图:一种常用的数据结构,代表了有限域中的稠集(dense set),每一个元素至少出现一次,没有其他的数据和元素相关联。在索引,数据压缩,海量数据处理等方面有...

25230
来自专栏编程坑太多

『高级篇』docker之Mesos集群架构图(23)

11840
来自专栏chenssy

多线程:为什么在while循环中加入System.out.println,线程可以停止

这个我们都知道,由于 stopReqested 的更新值在主内存中,而线程栈中的值不是最新的,所以会一直循环,线程并不能停止。加上 Volatile 关键字后,...

21440
来自专栏smy

一张图解释负载均衡

首先当大量用户访问时候,先请求到nignx服务器,因为nignx对于高并发支持较好,所以由nignx服务器将访问需求分配给不同的apache服务器,apache...

21330
来自专栏大数据文摘

迷人又诡异的辛普森悖论:同一个数据集是如何证明两个完全相反的观点的?

在辛普森悖论中,餐馆可以同时比竞争对手更好或更差,锻炼可以降低和增加疾病的风险,同样的数据集能够用于证明两个完全相反的论点。

15830
来自专栏数据结构笔记

python基础类型(一):字符串和列表

注意到最后三个的单双引号是嵌套使用的,但是最后一个的使用方法是错误的,因为当我们混合使用两种引号时必须有一种用来划分字符串的边界,即在两边的引号不能出现在字符串...

13920

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励