HDU 5971 Wrestling Match(二分图染色)

Ch_Zaqdt

发布于 2019-01-11 10:53:50

5000

文章被收录于专栏：Zaqdt_ACMZaqdt_ACM

题目链接：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;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018年11月03日，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历