峰会
题目描述
峰会是国家元首或政府首脑的会议。
为峰会安排休息区可不是一件简单的工作。
一共有 $N$ 个首脑参加峰会,编号 $1 \sim 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 \le N \le 200,$
$1 \le M \le N(N−1)2,$
$1 \le a, b \le N,$
$a \ne b,$
$1 \le K \le 100,$
$1 \le L \le N,$
同一对直接朋友关系不会在输入中重复出现。
输入样例:
8 10
5 6
7 8
6 4
3 6
4 5
2 3
8 2
2 7
5 3
3 4
6
4 5 4 3 6
3 2 8 7
2 2 3
1 1
2 4 6
3 3 2 1
输出样例:
Area 1 is OK.
Area 2 is OK.
Area 3 is OK.
Area 4 is OK.
Area 5 may invite more people, such as 3.
Area 6 needs help.
正解:枚举
$a, b$ 为直接朋友关系,就可以在 $a, b$ 之间连一条无向边,这可以用一个邻接矩阵来存(这道题中使用邻接矩阵效率较高)
然后我们判断输入的分组中是否每个人都和其他人之间有连边。如果没有,就说明是第三种情况。
然后我们按编号从小到大的顺序枚举每一个人(其实不用特判这个人是否在分组里,如果他在分组里那么他和它自己之间就没有连边),如果这个人和这个分组里的每一个人之间都有连边,那么就是第二种情况,$H$ 就是这个人的编号。
否则就是第一种情况。
AC Code
#include <iostream>
#define N 205
using namespace std;
int n, m, q, x, y, a[N];
bool flag, flag_, g[N][N];
int main ()
{
cin >> n >> m;
while (m --)
{
cin >> x >> y, g[x][y] = g[y][x] = 1;
}
cin >> q;
for (int kase = 1; kase <= q; kase ++)
{
cin >> x, flag = 0;
for (int i = 1; i <= x && !flag; i ++)
{
cin >> a[i];
for (int j = 1; j < i && !flag; j ++)
{
if (!g[a[i]][a[j]])
{
flag = 1;
}
}
}
if (flag)
{
cout << "Area " << kase << " needs help.\n";
continue;
}
for (int i = 1; i <= n; i ++)
{
flag_ = 1;
for (int j = 1; j <= x; j ++)
{
if (!g[i][a[j]])
{
flag_ = 0;
break;
}
}
if (flag_)
{
cout << "Area " << kase << " may invite more people, such as " << i << ".\n", flag = 1;
break;
}
}
if (flag)
{
continue;
}
cout << "Area " << kase << " is OK.\n";
}
return 0;
}
感谢观看!
$$\href {/blog/content/19548/} {\color {MediumSlateBlue} {【暑假每日一题】题解}}$$