模拟,枚举
$O(n^2)$
当然,这道题毫无算法优化可言
观察数据可以发现这道题的上限居然可以到$O(n^3)$,这一点毋庸置疑是暴力做法了
再看那么复杂的题目和要求限制,可以推断这道题考察基础的编码水平。
解题步骤:
- 将所有领导人之间的关系存在一个邻接矩阵里(双向);
- 判断每个方案是否符合两两都是朋友关系,是则去第3步,否就去第4步;
- 当发现符合时,一一枚举其他领导人是否有能够来休息室,如果有就输出第一个发现的那位,如果没有就输出当前的方案可以;
- 当发现不符时,那么直接输出需要调配
问题迎刃而解。
AC code
#include<iostream>
using namespace std;
const int N=210;
int g[N][N];
int r[N]; //rest休息区
int main()
{
int n,m; cin>>n>>m;
while(m--)
{
int a,b; cin>>a>>b;
g[a][b]=g[b][a]=1;
}
int T; cin>>T;
for(int ith=1;ith<=T;ith++)
{
int k; cin>>k;
for(int i=0;i<k;i++) cin>>r[i];
bool flag=1;
for(int i=0;i<k;i++)
for(int j=i+1;j<k;j++)
if(!g[r[i]][r[j]])
{
flag=0;
break;
}
if(!flag) printf("Area %d needs help.\n",ith);
else
{
int res=-1;
for(int i=1;i<=n;i++)
{
int j=0;
for(;j<k;j++)
if(!g[i][r[j]]) break;
if(j==k)
{
res=i;
break;
}
}
if(res!=-1) printf("Area %d may invite more people, such as %d.\n",ith,res);
else printf("Area %d is OK.\n",ith);
}
}
return 0;
}