Friend

admin管理员组

文章数量:1794759

Friend

题意：

在一个团队中如果有三个或更多人之间互相认识或互相不认识，那么这个团队就被称为”Bad Team”，否则被称为”Great Team”。给定一个团队的信息，然你判定这个团队是哪一种。

分析：

问题可以抽象为在一个点数为 N N $N$的无向图中是否存在一个完全图Kn" role="presentation">KnKn$K_n$（ Kn K n $K_n$代表定点数为 n n $n$的完全图。）,3&#x2264;n&#x2264;N" role="presentation">3≤n≤N3≤n≤N$3 \le n \le N$,又由于 Kn,3≤n≤N K n , 3 ≤ n ≤ N $K_n,3 \le n \le N$中必然包含 K3 K 3 $K_3$,所以问题最终转化为所给图中是否含有 K3 K 3 $K_3$.这就比较容易了。这道题还应用了拉姆齐定律，拉姆齐定律是这样的：6 个人中至少存在3人相互认识或者相互不认识。，那么当 n≥6 n ≥ 6 $n \ge 6$时，我就可以直接判定该队为Bad Team。这样我们就大大降低了复杂度。当 n<6 n < 6 $n \lt 6$ 时，我们首先从任一点出发进行dfs，看能否由此点出发找到 K3 K 3 $K_3$,其实也就是找到一个长度为3的环，能否找到这个环对应了是否含有三个人相互认识。而对于三个人相互不认识，我们可以将邻接矩阵中的1变为0，0变为1，再次进行上述寻找 K3 K 3 $K_3$的操作即可。

点此查看拉姆齐定理百度百科

代码：

#include <bits/stdc++.h>
#define FP(PP,QQ,RR) for(int PP = QQ;PP < RR;PP ++)
using namespace std;
int r,n;
int G[6][6],st;
vector <int> se;
bool dfs(int s){if(se.size() == 3){return G[s][st];}FP(i,s + 1,n){if(G[s][i]){se.push_back(i);if(dfs(i)) return true;else se.pop_back();}}return false;
}
bool solve(){memset(G,0,sizeof G);FP(i,0,n - 1)FP(j,i + 1,n){cin >> G[i][j];G[j][i] = G[i][j];}FP(i,0,n){st = i;se.push_back(i);if(dfs(i)) return true;se.clear();}FP(i,0,n){FP(j,0,n){if(i != j){G[i][j] = !G[i][j];}}}FP(i,0,n){st = i;se.push_back(i);if(dfs(i)) return true;se.clear();}return false;
}
int main(void)
{cin >> r;while(r --){cin >> n;if(n >= 6){int t,i = 0;while(i ++ < (n - 1) * n / 2){cin >> t;}}cout << ((n >= 6 || solve()) ? "Bad Team!" : "Great Team!") << endl;}return 0;
}

本文标签： friend