hdu5971——Wrestling Match(以二分图判定为主要思路的多种搞法)

时间：2022-03-29 19:37:26
Nowadays, at least one wrestling match is held every year in our country. There are a lot of people in the game is "good player”, the rest is "bad player”. Now, Xiao Ming is referee of the wrestling match and he has a list of the matches in his hand. At the same time, he knows some people are good players,some are bad players. He believes that every game is a battle between the good and the bad player. Now he wants to know whether all the people can be divided into "good player" and "bad player".
Input
Input contains multiple sets of data.For each set of data,there are four numbers in the first line:N (1 ≤ N≤ 1000)、M(1 ≤M ≤ 10000)、X,Y(X+Y≤N ),in order to show the number of players(numbered 1toN ),the number of matches,the number of known "good players" and the number of known "bad players".In the next M lines,Each line has two numbersa, b(a≠b) ,said there is a game between a and b .The next line has X different numbers.Each number is known as a "good player" number.The last line contains Y different numbers.Each number represents a known "bad player" number.Data guarantees there will not be a player number is a good player and also a bad player.
Output
If all the people can be divided into "good players" and "bad players”, output "YES", otherwise output "NO".
Sample Input 
5 4 0 0
1 3
1 4
3 5
4 5
5 4 1 0
1 3
1 4
3 5
4 5
2
Sample Output 
NO
YES
(引用)题意比较不明…看了很久才搞出来 个人理解 就是: 
n个人 给定m对关系:a,b不在一个集合中 
已知x个人是好球员的集合中的人 
y个人是坏球员 
判断是否能分成2个集合 
如果1是好球员 2是坏球员 
其余的球员与1,2无关系 能分成2个集合 也算YES
思路：判定二分图模板一上，先从确定阵营的人开始染色，如果矛盾，NO；
再把上次dfs还没确定的人染色，如果矛盾，NO；
最后检查有没有没确定阵营的，有的话，NO；
其余情况YES；
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cctype>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <climits>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define fi first
#define se second
#define ping(x,y) ((x-y)*(x-y))
#define mst(x,y) memset(x,y,sizeof(x))
#define mcp(x,y) memcpy(x,y,sizeof(y))
#define Min(x,y) (x<y?x:y)
#define Max(x,y) (x>y?x:y)
using namespace std;
#define gamma 0.5772156649015328606065120
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define N 5005
#define maxn 10005
typedef long long LL;
typedef pair<int,int> PII;

int pic[1001][1001];
int vis[200005],n,m;

void init(){
    for(int i=0;i<n;i++)
        vis[i]=-2;   //没有染色就是-2
    mst(pic,0);
}

int dfs(int x,int c){
    //if(vis[x]!=0&&vis[x]==c)return 0; //这模板有毒，这句让我WA吐血了
    vis[x]=c;
    for(int i=0;i<n;++i){
        if(pic[x][i]){
            if(vis[i]==0)
                dfs(i,-c);
            else if(vis[i]==c)return 0;
        }
    }
    return 1;
}
int main(){
    int i,j,group,Case=0,x,y,X,Y,a;
    while(scanf("%d%d%d%d",&n,&m,&X,&Y)!=EOF){
        init();
        //if(n==0)break;
        for(i=0;i<m;i++){
            scanf("%d%d",&x,&y);
            x--;y--;
            vis[x]=vis[y]=0;  //阵营不明确的
            pic[x][y]=pic[y][x]=1;
        }
        while(X--){scanf("%d",&a);a--;vis[a]=1;}//确定阵营的
        while(Y--){scanf("%d",&a);a--;vis[a]=-1;}//与上边对立
        bool flag=false;
        for(i=0;i<n;i++){
            if(vis[i]==1){
                if(!dfs(i,1)){flag=true;printf("NO\n");break;}
            }
            else if(vis[i]==-1){
                if(!dfs(i,-1)){flag=true;printf("NO\n");break;}
            }
        }
        if(flag)continue;
        for(i=0;i<n;i++){
            if(vis[i]==0){  //还剩的阵营不明确的再尝试分配，分给1和0都行
                if(!dfs(i,1)){flag=true;printf("NO\n");break;}
            }
        }
        if(flag)continue;
        for(i=0;i<n;i++){
            if(vis[i]==-2){
              flag=true;printf("NO\n");break;
            }
        }
        if(flag)continue;
        printf("YES\n");
    }
    return 0;
}
别人的二分图判断：

  
  
    

  1. #include<bits/stdc++.h>  
    2. 
   
   
  2. #include <cstdio>  
    3. 
   
   
  3. #include <algorithm>  
    4. 
   
   
  4. using namespace std;  
    5. 
   
   
  5. typedef long long ll;  
    6. 
   
   
  6. typedef pair<int,int> pll;  
    7. 
   
   
  7. const int N=5*1e4+1000;  
    8. 
   
   
  8. #define eps 1e-4  
    9. 
   
   
  9. int co[10005];  
    10. 
   
   
  10. int vis[10005];  
    11. 
   
   
  11. vector<int>g[10005];  
    12. 
   
   
  12. int dfs(int u)  
    13. 
   
   
  13. {  
    14. 
   
   
  14.     int sz=g[u].size();  
    15. 
   
   
  15.     for(int i=0; i<sz; i++)  
    16. 
   
   
  16.     {  
    17. 
   
   
  17.         int v=g[u][i];  
    18. 
   
   
  18.         if(!co[v])  
    19. 
   
   
  19.         {  
    20. 
   
   
  20.             co[v]=!co[u];  
    21. 
   
   
  21.             if(!dfs(v))  
    22. 
   
   
  22.                 return 0;  
    23. 
   
   
  23.         }  
    24. 
   
   
  24.         else if(co[u]==co[v])  
    25. 
   
   
  25.         {  
    26. 
   
   
  26.             return 0;  
    27. 
   
   
  27.         }  
    28. 
   
   
  28.     }  
    29. 
   
   
  29.     return 1;  
    30. 
   
   
  30. }  
    31. 
   
   
  31. int main()  
    32. 
   
   
  32. {  
    33. 
   
   
  33.     int n,m,x,y;  
    34. 
   
   
  34.     while(cin>>n>>m>>x>>y)  
    35. 
   
   
  35.     {  
    36. 
   
   
  36.         for(int i=0; i<10005; i++)  
    37. 
   
   
  37.             g[i].clear();  
    38. 
   
   
  38.         if(n==1)  
    39. 
   
   
  39.         {  
    40. 
   
   
  40.             puts("NO");  
    41. 
   
   
  41.             continue;  
    42. 
   
   
  42.         }  
    43. 
   
   
  43.         for(int i=0; i<m; i++)  
    44. 
   
   
  44.         {  
    45. 
   
   
  45.             int xx,yy;  
    46. 
   
   
  46.             scanf("%d%d",&xx,&yy);  
    47. 
   
   
  47.             g[xx].push_back(yy);  
    48. 
   
   
  48.         }  
    49. 
   
   
  49.         memset(co,0,sizeof(co));  
    50. 
   
   
  50.         for(int i=0; i<x; i++)  
    51. 
   
   
  51.         {  
    52. 
   
   
  52.             int xx;  
    53. 
   
   
  53.             scanf("%d",&xx);  
    54. 
   
   
  54.             co[xx]=1;  
    55. 
   
   
  55.         }  
    56. 
   
   
  56.         for(int i=0; i<y; i++)  
    57. 
   
   
  57.         {  
    58. 
   
   
  58.             int xx;  
    59. 
   
   
  59.             scanf("%d",&xx);  
    60. 
   
   
  60.             co[xx]=0;  
    61. 
   
   
  61.         }  
    62. 
   
   
  62.         if(x==0&&y==0)  
    63. 
   
   
  63.             puts("NO");  
    64. 
   
   
  64.         else  
    65. 
   
   
  65.         {  
    66. 
   
   
  66.             int flag=1;  
    67. 
   
   
  67.             for(int i=1; i<=n; i++)  
    68. 
   
   
  68.                 if(!dfs(i))  
    69. 
   
   
  69.                     flag=0;  
    70. 
   
   
  70.             if(flag)  
    71. 
   
   
  71.                 puts("YES");  
    72. 
   
   
  72.             else  
    73. 
   
   
  73.                 puts("NO");  
    74. 
   
   
  74.         }  
    75. 
   
   
  75.     }  
    76. 
   
   
  76.     return 0;  
    77. 
   
   
  77. }  
    78. 
  
  

别人的种类并查集:
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
typedef long long LL;
typedef unsigned long long ULL;


const int maxn=1005;


int N,M,X,Y;
int a,b;
int ok;
struct node{
    int father,rel;
}F[maxn];
bool vis[maxn];
int kind[maxn];


void init(){
    ok=1;
    memset(kind,-1,sizeof(kind));
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=N;i++){
        F[i].father=i;
        F[i].rel=0;
    }
}
int Find(int x){
    if(F[x].father==x)return x;
    int temp=F[x].father;
    F[x].father=Find(F[x].father);
    F[x].rel=F[x].rel^F[temp].rel;
    return F[x].father;
}
bool Uion(int x,int y){
    int fa,fb;
    fa=Find(x);
    fb=Find(y);
    F[fa].rel=F[x].rel^F[y].rel^1;
    if(fa==fb&&F[fa].rel!=0)return 0;
    if(fa!=fb)F[fa].father=fb;
    return 1;
}
bool go(int x){
    int fa=Find(x);
    if(kind[fa]>=0){
        return kind[fa]^kind[x]==F[x].rel;
    }
    else {
        kind[fa]=kind[x]^F[x].rel;
    }
}


int main()
{
    while(~scanf("%d%d%d%d",&N,&M,&X,&Y)){
        init();
        while(M--){
             scanf("%d%d",&a,&b);
             ok=(ok&&Uion(a,b));
             vis[a]=vis[b]=1;
        }
        while(X--){
            scanf("%d",&a);
            vis[a]=1;
            if(kind[a]==1)ok=0;
            else {
                kind[a]=0;
                ok=(ok&&go(a));
            }
        }
        while(Y--){
            scanf("%d",&a);
            vis[a]=1;
            if(kind[a]==0)ok=0;
            else {
                kind[a]=1;
                ok=ok&&go(a);
            }
        }
        for(int i=1;i<=N;i++){
            ok=(ok&&vis[i]);
        }
        if(ok){
              printf("YES\n");
        }
        else {
            printf("NO\n");
        }
    }
    return 0;
}
别人的并查集+dfs
并查集 
x的球员设置在集合1 y的在集合0 
先以x和y的球员作为起点 dfs确定球员关系 
如果dfs中发现关系矛盾 ->NO 
dfs完了 如果还有球员没确定集合 随便给一个没集合的球员设个集合 
以该球员作为起点dfs 
如果dfs完了 还有球员不能确定集合 ->NO 
否则YES 
坑爹的是!!!!!居然爆栈……… 
于是dfs改成队列…..就过了
#include<iostream>#include<stdlib.h>
#include<stdio.h>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<time.h>
#include<math.h>
#include<list>
#include<cstring>
#include<fstream>
//#include<memory.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define INF 1000000007
#define pll pair<ll,ll>
#define pid pair<int,double>

const int N=1000+5;
const int M=10000+5;

int par[N];
inline int find(int x){
return x==par[x]?x:par[x]=find(x);
}
vector<int>against[N];//against[i]保存与i不在一个集合的
vector<int>known;//保存x y的球员
bool visited[N];
bool dfs(int u){
deque<int>de;
    de.push_back(u);
while(!de.empty()){
        u=de[0];
        de.pop_front();
if(visited[u])
continue;
        visited[u]=true;
for(int i=0;i<against[u].size();++i){
int v=against[u][i];
if(par[v]<0){
                par[v]=1^par[u];
                de.push_back(v);
            }
else
if(par[v]+par[u]!=1)//矛盾
return false;
        }
    }
return true;
}

bool slove(int n){
for(int i=0;i<known.size();++i){//以x y中的球员作起点 找一遍
int u=known[i];
if(visited[i]==true)
continue;
if(dfs(i)==false)
return false;
    }
for(int i=1;i<=n;++i){//有球员没有与任何球员有对立关系 又不是已知good bad 必定NO
if(against[i].size()==0&&par[i]<0)
return false;
    }
int t=-1;//标记第一个没集合的球员
for(int i=1;i<=n;++i){
if(par[i]<0){
            t=i;
            par[t]=0;//设置成集合0
break;
        }
    }
if(t<0)//所有球员都有集合了
return true;
if(dfs(t)==false)
return false;
for(int i=1;i<=n;++i)//还有球员没集合
if(par[i]<0)
return false;
return true;
}

int main()
{
//freopen("/home/lu/文档/r.txt","r",stdin);
//freopen("/home/lu/文档/w.txt","w",stdout);
int n,m,x,y;
while(~scanf("%d%d%d%d",&n,&m,&x,&y)){
for(int i=1;i<=n;++i){
            par[i]=-1;
            visited[i]=false;
            against[i].clear();
        }
        known.clear();
for(int i=0,u,v;i<m;++i){
scanf("%d%d",&u,&v);
            against[u].push_back(v);
            against[v].push_back(u);
        }
for(int i=0,u;i<x;++i){
scanf("%d",&u);
            par[u]=1;//good=1
            known.push_back(u);
        }
for(int i=0,u;i<y;++i){
scanf("%d",&u);
            par[u]=0;//bad=0
            known.push_back(u);
        }
puts(slove(n)?"YES":"NO");
    }
return 0;
}

标签：

相关文章