本文主要是介绍HDU 3062 Party 基础，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem Description
有n对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有1人可以列席。在2n 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席？
Input
n： 表示有n对夫妻被邀请 (n<= 1000)
m： 表示有m 对矛盾关系 ( m < (n - 1) * (n -1))
在接下来的m行中，每行会有4个数字，分别是 A1,A2,C1,C2
A1,A2分别表示是夫妻的编号
C1,C2 表示是妻子还是丈夫 ，0表示妻子 ，1是丈夫
夫妻编号从 0 到 n -1
m： 表示有m 对矛盾关系 ( m < (n - 1) * (n -1))
在接下来的m行中，每行会有4个数字，分别是 A1,A2,C1,C2
A1,A2分别表示是夫妻的编号
C1,C2 表示是妻子还是丈夫 ，0表示妻子 ，1是丈夫
夫妻编号从 0 到 n -1
Output
如果存在一种情况 则输出YES
否则输出 NO
否则输出 NO
思想：找到矛盾点：夫妻。建边是找非矛盾点。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
using namespace std;
const int N=2000+5;
const int E=N*N*2;
int n,m;
struct node
{int v,next;
}e[E];
stack<int>s;
int head[N],cnt;
int dfn[N],low[N],instack[N],paint[N],col,index;
void Init()
{while(!s.empty()) s.pop();memset(head,-1,sizeof(head));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(instack,0,sizeof(instack));memset(paint,0,sizeof(paint));col=index=1;cnt=0;
}
void add(int a,int b)
{e[cnt].v=b;e[cnt].next=head[a];head[a]=cnt++;
}
int MIN(int a,int b)
{if(a<b) return a;return b;
}
void tarjan(int u)
{instack[u]=1;dfn[u]=low[u]=index++;s.push(u);for(int i=head[u];i+1;i=e[i].next){int v=e[i].v;if(!dfn[v]){tarjan(v);low[u]=MIN(low[u],low[v]);}else if(instack[v]){low[u]=MIN(low[u],dfn[v]);}}if(low[u]==dfn[u]){int k=s.top();while(k!=u){s.pop();paint[k]=col;instack[k]=0;k=s.top();}s.pop();paint[u]=col;instack[u]=0;col++;}
}
void Input()
{for(int i=1;i<=m;i++){//int a,b,c,d;//scanf("%d%d%d%d",&a,&b,&c,&d);//a=a*2+c;b=b*2+d;//add(a,b^1);add(b,a^1);int x,y,sex1,sex2;scanf("%d%d%d%d",&x,&y,&sex1,&sex2);if(sex1&&sex2){add(x+n,y);add(y+n,x);}if(!sex1&&sex2){add(x,y);add(y+n,x+n);}if(sex1&&!sex2){add(x+n,y+n);add(y,x);}if(!sex1&&!sex2){add(x,y+n);add(y,x+n);}}
}
void treatment()
{for(int i=0;i<2*n;i++){if(!dfn[i]) tarjan(i);}int mark=1;for(int i=0;i<n;i++){if(paint[i]==paint[i+n]){mark=0;break;}}if(mark) printf("YES\n");else printf("NO\n");
}
int main()
{while(~scanf("%d%d",&n,&m)){Init();Input();treatment();}return 0;
}
这篇关于HDU 3062 Party 基础的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
