SP2139题解

思路

这题数据范围小，暴力就可以了。

首先我们用 map 来统计每个人的下标，用 \(bk_{i,j}\) 表示第 \(i\) 个人第 \(j\) 题是否知道答案。

对于每次合作交流，暴力修改就可以了，先统计出两个人的下标，假设一个为 \(x\)，另一个为 \(y\)。
然后，如果 \(bk_{x,i}\) 和 \(bk_{y,i}\) 中（\(1\le i \le a\)），有一个是知道答案，那么就把两个都赋值为 \(1\)，也就是知道答案。

知道这些代码就很好写了，建议不要看，因为实在太简单。

AC CODE

#include <iostream>
#include<cstdio>
#include<map>
using namespace std;
int n,m,bk[2105][2105];
map<string,int>mp;
int main(){
	while(cin>>n>>m&&(n|m)){
		mp.clear();
		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)bk[i][j]=0;
		for(int i=1;i<=n;i++){
			string s;
			cin>>s;
			mp[s]=i;
			bk[i][i]=1;
		}
		for(int i=1;i<=m;i++){
			string a,b;
			cin>>a>>b;
			int x=mp[a],y=mp[b];
			for(int j=1;j<=n;j++){
				if(bk[x][j]||bk[y][j])bk[x][j]=bk[y][j]=1;
			}
		}
		bool flag=1;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(!bk[i][j])flag=0;
				if(!flag)break;
			}
			if(!flag)break;
		}
		if(flag)cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}