HDU 6152 Friend-Graph

题目链接【http://acm.hdu.edu.cn/showproblem.php?pid=6152】

题意：给出一个有3000个点的图，问你是否存在三个及以上的点两两没有边或者两两都有边。

正解：拉姆齐定理

　　拉姆齐定理：在组合数学上，要找到一个最小的数n,使得n个人中必定有x个人相互认识或y个人相互不认识。已知R(3,3) = 6;就是说只要人数大于6一定会有满足的条件，那么我们只需要暴力判断3-5个人中是否存在就可以了。

歪解：暴力判断，为了节省一个32的常数，我们用bitset判断是否有满足的条件。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int mp[7][7];
int T, N;
int main ()
{
    scanf("%d", &T);
    while(T--)
    {
        memset(mp, 0, sizeof(mp));
        scanf("%d", &N);
        if(N >= 6)
        {
            printf("Bad Team!
");
            for(int i = 1; i <= N; i++)
                for(int j = 1; j <= N - i; j++)
                {
                    int t;
                    scanf("%d", &t);
                }

        }
        else
        {
            for(int i = 1; i <= N; i++)
                for(int j = 1; j <= N - i; j++)
                {
                    int t;
                    scanf("%d", &t);
                    if(t == 1) mp[i][i + j] = mp[i + j][i] = 1;
                }
            bool fg = true;
            for(int i = 1; i <= N && fg; i++)
            {
                for(int j = 1; j <= N && fg; j++)
                {
                    if(i == j) continue;
                    for(int k = 1; k <= N && fg; k++)
                    {
                        if(i == k || j == k) continue;
                        if((mp[i][j] && mp[i][k] && mp[j][k]) || (!mp[i][j] && !mp[i][k] && !mp[j][k])) fg = false;
                    }
                }
            }
            if(fg) printf("Great Team!
");
            else printf("Bad Team!
");


        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 3005;
bitset<maxn>b[maxn];
int T, N;
bool check()
{
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= N; j++)
            if(b[i].test(j) && (b[i]&b[j]).any()) return true;
    return false;
}
int main ()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &N);
        for(int i = 1; i <= N; i++) b[i].reset();
        for(int i = 1; i <= N - 1; i++)
            for(int j = 1 + i; j <= N; j++)
            {
                int t;
                scanf("%d", &t);
                if(t) b[i].set(j), b[j].set(i);
            }
        if(check())
        {
            printf("Bad Team!
");
            continue;
        }
        else
        {
            for(int i = 1; i <= N - 1; i++)
                for(int j = 1 + i; j <= N; j++)
                    b[i].flip(j), b[j].flip(i);
            if(check())
            {
                printf("Bad Team!
");
                continue;
            }
            else
                printf("Great Team!
");
        }
    }
    return 0;
}