首页 > 代码库 > Wrestling Match hdu-5971（思维+STL）

Wrestling Match hdu-5971（思维+STL）

2024-10-02 23:37:39   217人阅读

Problem Description
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".
InputInput 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.OutputIf 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场比赛，已知其中有X个好人，Y个坏人。比赛一定是在好人和坏人之间进行的。问是否能够把n个人划分成好人和坏人两个部分？？

Input：
n,m,X,Y;接下来输入m行，每行输入两个数a和b，表示a和b之间进行了一场比赛。
Output：
如果能够把n个人分成好人和坏人两部分就输出YES；否则，输出NO。

思路：首先当a和b之间有比赛则说明a和b是对立的（即：若a好，则b坏；若a坏，则b好），所以凡是与a进行比赛的都是a的对立面。可以用vector容器进行统计a的对立都有哪些，进而把所有比赛人的对立都统计完全。

然后在输入好和坏的时候，分别这个人的对立（即vector[x]里的人）进行定义。如果是好（flag[x]=1），则vector[x]里的人全部是坏的(flag[t]=2)；反之，同理。
在flag标记的时候，如果有flag[t]=1,又需要把flag[t]定义成2时，则说明t不能够清楚的分为好or坏。因此，ans=-1（ans的初始值为0）。
判断完已知的好坏之后，会发现有些人还是不能够分清楚。对之前的比赛进行分类，如果比赛的两个人都不能分清楚，则把第一个人定义为1，然后对第一个人的所有对立进行定义；如果只是第一个人没有进行定义，就把第一个人定义成第二个人的对立，然后对第一个人的所有对立进行定义。
最后，对所有人的flag进行遍历，查看是否有人的flag没有被定义（是否有人根本没有出现）。
然后根据ans，决定最后的输出结果。

AC代码：

技术分享 
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <queue>
  5 #include <algorithm>
  6 #include <map>
  7 #include <set>
  8 #include <stdlib.h>
  9 #include <stack>
 10 #include <vector>
 11 #include <cmath>
 12 #define ll long long
 13 using namespace std;
 14 vector<int>vec[1005];
 15 int mp[10005];
 16 int a[10005][2];
 17 int main()
 18 {
 19     int n,m,c,b,x,y;
 20     while(~scanf("%d%d%d%d",&n,&m,&c,&b))
 21     {
 22         memset(mp,0,sizeof(mp));
 23         memset(a,0,sizeof(a));
 24         int flag=0;
 25         for(int i=0; i<m; i++)
 26         {
 27             scanf("%d%d",&x,&y);
 28             a[i][0]=x;
 29             a[i][1]=y;
 30             vec[x].push_back(y);
 31             vec[y].push_back(x);
 32         }
 33         for(int i=0; i<c; i++)
 34         {
 35             scanf("%d",&x);
 36             if(mp[x]!=2)
 37                 mp[x]=1;
 38             else
 39                 flag=1;
 40             for(int j=0; j<vec[x].size(); j++)
 41             {
 42                 if(mp[vec[x][j]]!=1)
 43                     mp[vec[x][j]]=2;
 44                 else
 45                     flag=1;
 46             }
 47         }
 48         for(int i=0; i<b; i++)
 49         {
 50             scanf("%d",&x);
 51             if(mp[x]!=1)
 52                 mp[x]=2;
 53             else
 54                 flag=1;
 55             for(int j=0; j<vec[x].size(); j++)
 56             {
 57                 if(mp[vec[x][j]]!=2)
 58                     mp[vec[x][j]]=1;
 59                 else
 60                     flag=1;
 61             }
 62         }
 63         if(flag)
 64         {
 65             printf("NO\n");
 66         }
 67         else
 68         {
 69             for(int i=0; i<m; i++)
 70             {
 71                 if(mp[a[i][0]]==0&&mp[a[i][1]]==0)
 72                     mp[a[i][0]]=1;
 73                 else if(mp[a[i][0]]==0)
 74                 {
 75                     mp[a[i][0]]=mp[a[i][1]]%2+1;
 76                 }
 77                 x=a[i][0];
 78                 y=mp[x]%2+1;
 79                 for(int j=0; j<vec[a[i][0]].size(); j++)
 80                 {
 81                     if(mp[vec[x][j]]!=y%2+1)
 82                         mp[vec[x][j]]=y;
 83                     else
 84                         flag=1;
 85                 }
 86             }
 87             for(int i=1; i<=n; i++)
 88             {
 89                 if(mp[i]==0)
 90                 {
 91                     flag=1;
 92                     break;
 93                 }
 94             }
 95             if(flag)
 96                 printf("NO\n");
 97             else
 98                 printf("YES\n");
 99         }
100     }
101     return 0;
102 }
View Code

 


 





 
Wrestling Match hdu-5971（思维+STL）






























        

            
                
                  
                
                

                    联系

                    我们