4278.峰会

caution

原题链接：https://www.acwing.com/problem/content/4281/

思路

仔细读题发现，总共有三种情况：

1. 先满足任意两个人之间都是朋友关系，并且不存在继续加入一个人使得任意两人之间仍然是朋友关系。
2. 先满足任意两个人之间都是朋友关系，但是在其他人当中存在再加入一个人使得任意两人之间仍然是朋友关系，输出这个加入的人的 id（最小的一个就行）。
3. 无法满足任意两个人之间都是朋友关系。

所以理解题目之后发现其实就是找图中的边，先把朋友关系图存起来，然后枚举所有的边即可。枚举满足上面三种情况分别进行输出即可。可以按照下面的思路枚举：

1. 先枚举是否满足任意两人之间都是朋友关系
2. 如果满足，则再枚举在其他人当中还有没有再加入一个人继续使得任意两人之间是朋友关系。
   • 如果满足，则输出可以邀请更多的人，输出最小的编号
   • 如果不满足，则该区域就是 ok 的
3. 如果不满足，则直接输出不符合安排，需要帮助。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 210;

int n, m, k;
int g[N][N];

int main() {
    freopen("in.txt", "r", stdin);
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a][b] = g[b][a] = true;
    }

    cin >> k;

    int a[N];
    for (int i = 1; i <= k; i++) {
        int l;
        cin >> l;
        for (int j = 1; j <= l; j++)
            cin >> a[j];

        bool flag = true;
        // 先找现在这个关系是不是彼此相互都是朋友关系
        for (int j = 1; j <= l; j++)
            for (int k = j + 1; k <= l; k++) {
                cout << a[j] << " " << a[k] << " " << g[a[j]][a[k]] << endl;
                if (!g[a[j]][a[k]]) {
                    flag = false;
                    break;
                }
            }

        if (!flag)
            printf("Area %d needs help.\n", i);
        else {
            flag = false;
            int id;
            // 当满足彼此都是朋友关系之后看是否有其他人跟现在有的人是不是也是彼此相互是朋友关系
            // 也就是看再加入一个人是否还能保证彼此之间都是朋友关系
            for (int j = 1; j <= n; j++) {
                bool is_friend = true;
                // 从 1 - n 中找还有哪些朋友
                for (int k = 1; k <= l; k++) {
                    cout << j << " " << a[k] << g[j][a[k]] << endl;
                    if (!g[j][a[k]]) {
                        is_friend = false;
                        break;
                    }
                }
                // 如果加入一个人，并且仍然构成彼此之间是朋友，那就可以加入
                if (is_friend) {
                    flag = true;
                    id = j;
                    break;
                }
            }
            if (flag)
                printf("Area %d may invite more people. such as %d.\n", i, id);
            else
                printf("Area %d is OK.\n", i);
        }
    }

    return 0;
}