PTA 1166 Summit (25 分)

本文主要是介绍PTA 1166 Summit (25 分)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1166 Summit (25 分)

A summit (峰会) is a meeting of heads of state or government. Arranging the rest areas for the summit is not a simple job. The ideal arrangement of one area is to invite those heads so that everyone is a direct friend of everyone.

Now given a set of tentative arrangements, your job is to tell the organizers whether or not each area is all set.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N (≤ 200), the number of heads in the summit, and M, the number of friendship relations. Then M lines follow, each gives a pair of indices of the heads who are friends to each other. The heads are indexed from 1 to N.

Then there is another positive integer K (≤ 100), and K lines of tentative arrangement of rest areas follow, each first gives a positive number L (≤ N), then followed by a sequence of L distinct indices of the heads. All the numbers in a line are separated by a space.

Output Specification:

For each of the K areas, print in a line your advice in the following format:

if in this area everyone is a direct friend of everyone, and no friend is missing (that is, no one else is a direct friend of everyone in this area), print Area X is OK..

if in this area everyone is a direct friend of everyone, yet there are some other heads who may also be invited without breaking the ideal arrangement, print Area X may invite more people, such as H. where H is the smallest index of the head who may be invited.

if in this area the arrangement is not an ideal one, then print Area X needs help. so the host can provide some special service to help the heads get to know each other.

Here X is the index of an area, starting from 1 to K.

Sample Input:

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

Sample Output:

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.

感悟

这鸟题目的英文看不懂,对着翻译都看不懂,只能说有道翻译真烂,我的英语也真烂,看懂了题意其实不难,200的数据范围,就直接暴力点过了,本来想着用并查集,但是后面发现需要是直接朋友,所以就只能建图,然后暴力枚举一下.这题代码写的也是有够丑的,有机会再优化一下.

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

const int N = 210;

int n, m;
int a[N];
int b[N][N];

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1 ; i <= n ; i ++) a[i] = i;
    for(int i = 0; i < m; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        b[x][y] = b[y][x] = 1;
    }
    scanf("%d", &m);
    for(int i = 1 ; i <= m ; i ++)
    {
        int l, flag = 0;
        int st[N] = {0};
        scanf("%d", &l);
        for(int j = 1 ; j <= l ; j ++)
            scanf("%d",&a[j]),st[a[i]] = 1;
        for(int j = 1 ; j <= l && !flag; j ++)
            for(int k = j + 1 ; k <= l ; k ++)
                if(b[a[j]][a[k]] == 0)
                    flag = 1;
        if(flag) printf("Area %d needs help.\n",i);
        else 
        {
            for(int j = 1 ; j <= n && !flag; j++)
            {
                if(st[j])continue;
                int cnt = 0;
                for(int k = 1 ; k <= l; k ++)
                    if(b[j][a[k]] == 0) break;
                    else if(k == l)printf("Area %d may invite more people, such as %d.\n", i, j),flag = 1;;
            }
            if(!flag)printf("Area %d is OK.\n",i);
        }
    }

    return 0;
}

这篇关于PTA 1166 Summit (25 分)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！