题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5971
题意是有n个人,m个匹配,x个good player,y个bad player,每一个匹配都有一个good player和一个bad player,问能不能根据已知信息把这n个人分成两个集合。
思路就是用染色的方法去判断能不能构成一个二分图,我们首先将col数组初始化为0,然后输入x个good player时赋值为1,输入y个bad player时赋值为-1,然后我们根据当前已知的点,去判断一个图能否构成二分图,如果不行输出NO,在所有的已知点判断完后,再次遍历所有点,找还没有标记过的点随便赋值为good or bad,然后再去判断是否能构成二分图,如果不能输出NO。至于判断是不是二分图,上模板就好了,我是用bfs去跑的...
AC代码:
#include <bits/stdc++.h>
#define maxn 200005
using namespace std;
vector<int> G[maxn];
int col[maxn];
int n,m,x,y;
void init(){
for(int i=0;i<=n;i++){
G[i].clear();
col[i] = 0;
}
}
bool bfs(int x){
queue<int> q;
q.push(x);
while(!q.empty()){
int v = q.front();
q.pop();
for(int i=0;i<G[v].size();i++){
int xx = G[v][i];
if(col[xx] == 0){
col[xx] = -col[v];
q.push(xx);
}
if(col[xx] == col[v]){
return false;
}
}
}
return true;
}
int main()
{
while(~scanf("%d%d%d%d",&n,&m,&x,&y)){
init();
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
int xx;
for(int i=0;i<x;i++){
scanf("%d",&xx);
col[xx] = 1;
}
for(int i=0;i<y;i++){
scanf("%d",&xx);
col[xx] = -1;
}
if((x == 0 && y == 0) || n == 1){
puts("NO");
continue;
}
bool flag = true;
for(int i=1;i<=n;i++){
if(col[i] && !bfs(i)){
flag = false;
break;
}
}
for(int i=1;i<=n;i++){
if(col[i] == 0){
col[i] = 1;
if(!bfs(i)){
flag = false;
break;
}
}
}
if(flag == false)puts("NO");
else puts("YES");
}
return 0;
}