题目描述

峰会是国家元首或政府首脑的会议。

为峰会安排休息区可不是一件简单的工作。

一共有 N 个首脑参加峰会，编号 1∼N。

这些首脑之间存在 M 对两两之间的直接朋友关系。

在划分区域时，我们希望被安排在同一休息区域的首脑们满足，任意两人之间都是直接朋友关系。

现在，给定 K 个关于划分休息区域的安排，请你依次判断每个安排是否合理。

输入格式
第一行包含两个整数 N 和 M。

接下来 M 行，每行包含两个整数 a,b，表示首脑 a 和首脑 b 之间存在直接朋友关系。

再一行包含整数 K。

接下来 K 行，每行描述一个区域安排，首先包含一个整数 L，表示该安排打算将 L 个首脑安排在同一区域休息，然后包含 L 个整数，表示这些首脑的编号。

输出格式
共 K 行，第 i 行输出对第 i 个安排的判断，具体格式为

如果安排满足其中的任意两人之间都是直接朋友关系并且不存在额外的人与被安排的所有人都是直接朋友关系（即无法安排更多的人在这一区域休息），则输出 Area X is OK.
如果安排满足其中的任意两人之间都是直接朋友关系并且存在额外的人与被安排的所有人都是直接朋友关系（即可以安排更多的人在这一区域休息），则输出 Area X may invite more people, such as H.，其中 H 是额外可被安排的人的编号（如果不唯一，则输出最小的那个）。
如果安排无法满足其中的任意两人之间都是直接朋友关系，则输出 Area X needs help.。
X 表示组别编号，从 1 到 K。

数据范围
1≤N≤200,
1≤M≤N(N−1)2,
1≤a,b≤N,
a≠b,
1≤K≤100,
1≤L≤N,
同一对直接朋友关系不会在输入中重复出现。

思路

①一开始使用邻接矩阵来存储两人之间是否是朋友关系这一点确实想到了。这是一道模拟题，最后的解分为三种情况，即“恰好”、“不合适”、“还可以更多人”。
②“不合适”最好想，直接在长度为k的数组中两两枚举是否是朋友关系即可。
③“恰好”和“还可以更多人”应该放到一起判断，经过②的循环，现在的k数组中每个人两两之间一定是朋友关系，只需要判断是否可以放更多的人即可。方法是枚举每一个人（从1~n，数据量是200，不会超时），第二层循环枚举长度为k的组中的每个人的编号，看看外面的人和组内的人是否有朋友关系。注意，如果有一个人没有，那么就不满足两两之间的朋友关系，直接判断n中的下一个人即可。如果k外面的某个人与组内的每个人都是朋友关系，说明他可以加入，否则Area is OK。

代码

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 205;
const int maxm = 20005;
int n, m, k;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	int fr[maxn][maxn] = { 0 };
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		fr[a][b] = fr[b][a] = 1;
	}
	cin >> k;
	for (int i = 1; i <= k; i++) {
		int l;
		cin >> l;
		int q[maxn] = { 0 };
		for (int j = 1; j <= l; j++) {
			cin >> q[j];
		}
		bool isOk = true;
		for (int x = 1; x <= l; x++) {
			for (int y = x + 1; y <= l; y++) {
				if (!fr[q[x]][q[y]]) {
					isOk = false;
					break;
				}
			}
		}
		if (!isOk) {
			cout << "Area " << i << " needs help."<<endl;
		}
		else {
			int frnm;
			for (int x = 1; x <= n; x++) {
				bool isfr = true;
				for (int y = 1; y <= l; y++) {
					if (!fr[x][q[y]]) {
						isfr = false;
						break;
					}
				}
				if (isfr) {
					isOk = false;
					frnm = x;
					break;
				}
			}
			if (!isOk) {
				cout << "Area " << i << " may invite more people, such as " << frnm << "." << endl;
			}
			else {
				cout << "Area " << i << " is OK." << endl;
			}
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65