2016ACM/ICPC亚洲区大连站-pro.A Wrestling Match HDU - 5971 （思维+dfs）

题目链接

n 个人，m 场 比赛 ，x 个已经确定的好人 ，y  个已经确定的坏人。

每场比赛固定由好人和坏人匹配。问是否能够将每个人划分成好人或者坏人。

先从已经确定角色的人开始标记与其相关的人,冲突就NO；

然后对于不确定的人，枚举两种情况标记，冲突就NO；

如果最后还存在不确定的，那么就NO；

否则就是 YES 

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f;
const int N=1010;
int n,m,x,y;
vector<int>g[N]; //oppontents
int tab[N];
void init(){ //init
for(int i=0;i<n;i++){
g[i].clear();
tab[i]=-inf;
}
}
bool dfs(int u,int _tab){
tab[u]=_tab;
for(int i=0;i<g[u].size();i++){ //conflict
if(tab[g[u][i]]==_tab)
return false;
if(tab[g[u][i]]==0&&!dfs(g[u][i],-_tab))
return false;
}
return true;
}
void work(){
for(int i=0;i<n;i++){
if(tab[i]==1){ //good
if(!dfs(i,1)){ //conflict
printf("NOn");
return ;
}
}
else if(tab[i]==-1){ //bad
if(!dfs(i,-1)){
printf("NOn");
return ;
}
}
}
for(int i=0;i<n;i++){
if(tab[i]==0){ //unkown
if(!dfs(i,1)){
printf("NOn");
return ;
}
}
}
for(int i=0;i<n;i++){ //left
if(tab[i]==-inf){
printf("NOn");
return ;
}
}
printf("YESn");
//	return ;
}
int main(){
while(~scanf("%d%d%d%d",&n,&m,&x,&y)){
init();
int a,b;
for(int i=0;i<m;i++){
scanf("%d%d",&a,&b);
a--;b--;
tab[a]=0;tab[b]=0;
//unkown identity
g[a].push_back(b);
g[b].push_back(a);
}
for(int i=0;i<x;i++){ //good
scanf("%d",&a);
a--;
tab[a]=1;
}
for(int i=0;i<y;i++){ //bad
scanf("%d",&a);
a--;
tab[a]=-1;
}
work();
}
return 0;
}

最后

以上就是粗暴康乃馨为你收集整理的2016ACM/ICPC亚洲区大连站-pro.A Wrestling Match HDU - 5971 （思维+dfs）的全部内容，希望文章能够帮你解决2016ACM/ICPC亚洲区大连站-pro.A Wrestling Match HDU - 5971 （思维+dfs）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。