2017CCPC网络赛 Friend

网络赛 Friend"/>

2017CCPC网络赛 Friend

题意：

给出n个人之间的关系，如果其中有三个人互相认识或者互相不认识，则输出 Bad Team! ，否则输出 Great Team! 

思路：

很明显其实就是求一个无向图的最大团或者其最大独立集数是否>=3，但是会超时。这里用到了一个拉姆齐（Ramsey）定理，其通俗表述为6个人中至少存在3人相互认识或者相互不认识。

所以>=6直接特判bad team，否则再暴力求即可。但是最暴力的解法也能过！！枚举一个点，然后枚举其相连的点，判断其相连的点之间是否相连，判断一下就可以了，同样地最后补图再搞一遍。

补充：bool类型只占一个字节= =。

代码：

#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 3005;
vector<int> G1[maxn], G2[maxn];
int N;
int root;
int find1(int u, int dep, int father)
{if(dep == 3) return root == u;int len = G1[u].size();for(int i = 0; i < len; ++i){int v = G1[u][i];if(v == father) continue;if(find1(v, dep+1, u)) return 1;}return 0;
}
int find2(int u, int dep, int father)
{if(dep == 3) return root == u;int len = G2[u].size();for(int i = 0; i < len; ++i){int v = G2[u][i];if(v == father) continue;if(find2(v, dep+1, u)) return 1;}return 0;
}
int mapping()
{int x;scanf("%d", &N);for(int i = 1; i <= N && N < 6; ++i)G1[i].clear(), G2[i].clear();for(int i = 1; i <= N; ++i){for(int j = 1; j <= N-i; ++j){scanf("%d", &x);if(N >= 6) continue;if(x){G1[i+j].push_back(i);G1[i].push_back(i+j);}else{G2[i+j].push_back(i);G2[i].push_back(i+j);}}}if(N >= 6) return 1;for(int i = 1; i <= N; ++i){root = i;if(find1(i, 0, -1)) return 1;}for(int i = 1; i <= N; ++i){root = i;if(find2(i, 0, -1)) return 1;}return 0;
}
int main()
{int tt; scanf("%d", &tt);for(int _ = 1; _ <= tt; ++_){if(mapping()) puts("Bad Team!");else puts("Great Team!");}return 0;
}/********************************************///n^3暴力
#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 3005;
bool mp[maxn][maxn], vis[maxn][maxn];
int T, N;
template <class T>  
inline void _cin1(T &ret)
{  char c;   ret = 0;  while((c = getchar()) < '0' || c > '9');  while(c >= '0' && c <= '9')  {   ret = ret * 10 + (c - '0');  c = getchar();  }  
}
bool work()
{scanf("%d", &N);for(int i = 1; i <= N; ++i){for(int j = 1; j <= N-i; ++j){int x; _cin1(x);mp[i][i+j] = mp[i+j][i] = x;}}memset(vis, 0, sizeof vis);for(int i = 1; i <= N; ++i){for(int j = i+1; j <= N; ++j){if(mp[i][j]){for(int k = j+1; k <= N; ++k){if(mp[i][k] && mp[j][k]) return 1;}}}for(int j = i+1; j <= N; ++j){if(!mp[i][j]){for(int k = j+1; k <= N; ++k){if(!mp[i][k] && !mp[j][k]) return 1;}}}}return 0;
}
int main()
{//freopen("in.txt", "r", stdin);scanf("%d", &T);for(int _ = 1; _ <= T; ++_){if(work()) puts("Bad Team!");else puts("Great Team!");}return 0;
}

继续加油~