AcWing 4278. 峰会

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 4278. 峰会原题链接简单

作者：

iwoeix , 2022-06-17 16:36:00 , 所有人可见 , 阅读 1060

26

1

<---大佬们点个赞吧qwq

$\huge\color{orange}{→→→暑假每日一题2022题解合集←←←}$
$\$
$\$

题目描述

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

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

一共有 $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 \\frac{N(N-1)}{2}$ ,
$1 \\le a,b \\le N$ ,
$a \\neq b$ ,
$1 \\le K \\le 100$ ,
$1 \\le L \\le N$ ,
同一对直接朋友关系不会在输入中重复出现。

输入样例：

输出样例：

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.

算法

(暴力枚举) $O(n^2k)$

这道题数据范围非常小，暴力即可。
1. 枚举这一区域的任意两位首脑是否都是朋友。
2. 如果不是，直接输出 Area X needs help.。
3. 否则，枚举其他首脑能否到这个休息区。
4. 如果没有首脑能加入则输出 Area X is OK.。
5. 否则输出 Area X may invite more people, such as H.，其中 H 是额外可被安排的人的编号（如果不唯一，则输出最小的那个）。

时间复杂度

读入要花费 $O(m)$ 的时间（也就是 $O(n^2)$ ），要判断 $k$ 次，每次判断两位首脑需要 $O(l^2)$ ，枚举其他首脑能否到这个休息区需要 $O(nl)$ ，由于 $n$ 是 $l$ 的上界，所以总的时间复杂度就是 $O(n^2k)$ 。

空间复杂度

邻接矩阵一共要存 $O(n^2)$ 个关系，每个休息区最多有 $O(n)$ 位首脑，所以空间复杂度就是 $O(n^2)$ 。

C++ 代码

#include <iostream>

using namespace std;

const int N = 210;

int n, m, K; // n, m, k如题意
bool g[N][N]; // 邻接矩阵
int a[N]; // 休息区

int main()
{
    cin >> n >> m;
    while (m -- ) // 读入每个朋友关系
    {
        int i, j;
        cin >> i >> j;
        g[i][j] = g[j][i] = true;
    }

    cin >> K;
    for (int i = 1; i <= K; i ++ ) // 逐一判断休息区
    {
        int l;
        cin >> l;
        for (int j = 0; j < l; j ++ ) cin >> a[j]; // l位首脑

        bool flag = false; // 是否无法满足其中的任意两人之间都是直接朋友关系
        for (int j = 0; j < l - 1; j ++ )
            for (int k = j + 1; k < l; k ++ )
                if (!g[a[j]][a[k]]) // a[j]和a[k]如果不是朋友
                    flag = true; // 标记一下

        if (flag) // 如果无法满足其中的任意两人之间都是直接朋友关系
        {
            cout << "Area " << i << " needs help.\n";
            continue;
        }

        flag = false; // 能否可以安排更多的人在这一区域休息
        int idx; // 安排的人的编号
        for (int j = 1; j <= n; j ++ ) // 枚举所有人
        {
            bool f = true; // 他是否和休息区里的所有人都是朋友
            for (int k = 0; k < l; k ++ ) // 枚举休息区里的所有人
                if (!g[j][a[k]]) // 如果j和a[k]不是朋友
                {
                    f = false; // 标记
                    break; // 退出循环
                }

            if (f) // 如果j和休息区里的所有人都是朋友
            {
                flag = true, idx = j; // 标记
                break; // 退出循环
            }
        }

        if (flag) cout << "Area " << i << " may invite more people, such as " << idx << ".\n"; // 输出答案
        else cout << "Area " << i << " is OK.\n";
    }

    return 0;
}

9 评论

iwoeix 2022-06-17 16:41

有人可能会有疑问：为什么枚举其他首脑能否到这个休息区的时候不用排除已经在休息区里的首脑呢？
答案很简单：因为自己不会和自己是朋友，所以在遍历的时候就把他排除了

acwing_1482 2022-07-28 00:13

大佬，加continue是什么原因?

iwoeix 2022-07-28 07:14

后面不要判断了啊，要不然的话这个程序可能就会输出两遍

Hikario 2022-07-14 18:17

我们思路真的好像[doge]

#include<iostream>
#include<queue>
using namespace std;
const int N=220;
bool are_friends[N][N];
int a[N],q[N],top=0;
int main()
{
    int n,m,x,y;
    cin>>n>>m;
    for(int i=1;i<=n;i++)are_friends[i][i]=true;
    for(int i=1;i<=m;i++)scanf("%d%d",&x,&y),are_friends[x][y]=true,are_friends[y][x]=true;
    int p;
    cin>>p;
    for(int u=1;u<=p;u++)
    {
        int k;
        cin>>k;
        bool st[N]={false};
        for(int i=1;i<=k;i++)scanf("%d",&a[i]),st[a[i]]=true;
        bool flag=true;
        for(int i=1;i<=k;i++)
        {
            for(int j=1;j<=k;j++)
            {
                flag=are_friends[a[i]][a[j]];
            }
            if(flag==false)break;
        }
        if(flag==false)printf("Area %d needs help.\n",u);
        else
        {
            int accept_member=-1;
            for(int i=1;i<=n;i++)
            {
                if(st[i]==true)continue;
                bool flag=true;
                for(int j=1;j<=k;j++)
                {
                    if(are_friends[i][a[j]]==false)
                    {
                        flag=false;
                        break;
                    }
                }
                if(flag==true)
                {
                    accept_member=i;
                    break;
                }
            }
            if(accept_member==-1)printf("Area %d is OK.\n",u);
            else printf("Area %d may invite more people, such as %d.\n",u,accept_member);
        }
    }
    return 0;
}

小宋最可爱 2022-07-13 12:17

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,k;
const int N = 200;
const int K = 100;
int p[N][N];//无向图，存放朋友关系
int rest[K];//休息区安排情况
bool flag=true;
int zu;//记录可以邀请的首脑编号
int main()
{
    // memset(p,0,sizeof(p));//初始化p
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        p[i][j]=0;
    }
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        p[a][b]=p[b][a]=1;
    }
    cin>>k;
    for(int i=0;i<k;i++)
    {
        flag=true;
        int a;
        cin>>a;
        for(int j=0;j<a;j++)
        {
            cin>>rest[j];
        }

        for(int j=0;j<a-1;j++)//判断是否任意两人之间都是朋友
        {
            int x=rest[j];
            for(int t=j+1;t<a;t++)
            {
                int y=rest[t];
                if(!p[x][y])
                {
                    flag=false;
                    break;
                }
            }
            if(!flag)
            {
                cout<<"Area "<<i+1<<" needs help."<<endl;
                break;
            }

        }
        if(flag)//如果任意两个人都是朋友,判断是否可以多邀请
        {
            zu=0;
            flag=false;
            for(int j=0;j<n;j++)//遍历所有首脑
        {
            bool f=true;
            // flag=false;
            for(int l=0;l<a;l++)//查看是否与休息区均为朋友
            {
                if(!p[j+1][rest[l]])//如果该首脑与其中一个不是朋友的话标记false,跳出循环
                {
                    f=false;
                break;
                }


            }
            if(f)
            {
                flag=true;
                zu=j+1;
                break;
            }

        }
        if(flag) cout<<"Area "<<i+1<<" may invite more people, such as "<<zu<<'.'<<endl;
        else cout<<"Area "<<i+1<<" is OK."<<endl;
        }

    }
    return 0;
}