CCPC网赛 Friend-Graph（图论+模拟+输入外挂）

朱雀 2022-06-10 12:49 85阅读 0赞

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

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 n≤3000)  
  
Then there are n-1 rows. The i ith row should contain n-i numbers, in which number aij aijrepresents the relationship between member i and member j+i. 0 means these two individuals are not friends. 1 means these two individuals are friends.

Output

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

Sample Input

1
    4
    1 1 0
    0 0
    1

Sample Output

Great Team!

题解：

首先纪念一下第一次打CCPC网络赛，qaq只A了一题的弱渣

题意：

每一行给出第i个人与i+j个人的关系情况，求出是否是一个好队

首先这题题目理解了好久。。一开始还理解错了

坏队条件：

对于每一个人，只要出现如果队里有3个或者以上没有直接朋友关系的人就是坏队

对于一个队，如果出现有3个人都互相认识的队是坏队

经过分析可以转化成图的信息：

有三元环的图不符合要求（注意只是三元环），对于每一个节点，如果有总节点数n-与直接它相连的点num>=3就不符合要求

明白这两点就好做了，这一题输入数据很大，这里用了输入的外挂可以提高很多速度，这一题用了1sAC的

然后我的思路是因为输入的每一层都和之前的人没关系了，所以这相当于一颗树（也不是树），因为只要判断3元关系，我们只要前一层和当前层出现的数字不能相同就好了（我画图得出的结论）

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    #define INF 1008611111
    #define ll long long
    #define eps 1e-15
    int vis1[3005];
    int vis2[3005];
    int num[3005];
    void scan_d(int& ret)//输入外挂
    {
        char c;
        ret=0;
        while((c=getchar())<'0'||c > '9');
        while(c>='0'&&c<='9')
        {
            ret=ret*0+(c-'0'),c=getchar();
        }
    }
    int main()
    {
        int i,j,n,d,test,tag;
        scanf("%d",&test);
        while(test--)
        {
            tag=1;
            scanf("%d",&n);
            for(i=1;i<=n;i++)
            {
                num[i]=1;
                vis1[i]=0;
                vis2[i]=0;
            }
            for(i=1;i<=n-1;i++)
            {
                for(j=i+1;j<=n;j++)
                {
                    scan_d(d);
                    if(d==1&&tag)
                    {
                        num[i]++;//存每个节点有多少个点与他直接相连（包括自己）
                        num[j]++;
                        if(vis1[j])//vis1表示上一层的数字出现情况
                            tag=0;
                        vis2[j]=1;//表示当层数字出现情况
                    }
                }
                if(tag)
                {
                    for(j=i+1;j<=n;j++)
                    {
                        vis1[j]=vis2[j];
                        vis2[j]=0;
                    }
                }
            }
            for(i=1;i<=n;i++)
            {
                if(n-num[i]>=3)//对于每一个节点不能有3个或者以上没有与他直接相连的点
                {
                    tag=0;
                    break;
                }
            }
            if(tag)
                printf("Great Team!\n");
            else
                printf("Bad Team!\n");
        }
        return 0;
    }