Party
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3551 Accepted Submission(s): 1154
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
Sample Input
2
1
0 1 1 1
Sample Output
YES
Source
2-sat
模型一：两者（A，B）不能同时取
那么选择了A就只能选择B’，选择了B就只能选择A’
连边A→B’，B→A’
模型二：两者（A，B）不能同时不取
那么选择了A’就只能选择B，选择了B’就只能选择A
连边A’→B，B’→A
模型三：两者（A，B）要么都取，要么都不取
那么选择了A，就只能选择B，选择了B就只能选择A，选择了A’就只能选择B’，选择了B’就只能选择A’
连边A→B，B→A，A’→B’，B’→A’
模型四：两者（A，A’）必取A
连边A’→A
#include <iostream> #include <stdio.h> #include <queue> #include <stdio.h> #include <string.h> #include <vector> #include <queue> #include <set> #include <algorithm> #include <map> #include <stack> #include <math.h> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) #pragma comment(linker, "/STACK:10240000000000,10240000000000") using namespace std; typedef long long LL ; const int Max_N=2008 ; const int Max_M=2000008 ; int id ; int vec[Max_N] ,mystack[Max_N] ,top; int low[Max_N] ,dfn[Max_N] ,idx ,num ; bool instack[Max_N] ; int belong[Max_N] ; //belong[i] ,i为哪个联通分量 //int sum[Max_N] ; //缩点后每个联通分量中点的个数 struct Edge{ int v ; int next ; }; Edge edge[Max_M] ; inline void add_edge(int u,int v){ edge[id].v=v ; edge[id].next=vec[u] ; vec[u]=id++ ; } void tarjan(int u){ low[u]=dfn[u]=idx++ ; mystack[++top]=u ; instack[u]=1 ; for(int e=vec[u];e!=-1;e=edge[e].next){ int v=edge[e].v ; if(dfn[v]==-1){ 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 v ; num++ ; do{ v=mystack[top--] ; instack[v]=0 ; belong[v]=num ; // sum[num]++ ; }while(v!=u) ; } } void init(){ idx=1 ; top=-1 ; num=0 ; id=0; memset(dfn,-1,sizeof(dfn)) ; memset(vec,-1,sizeof(vec)) ; memset(instack,0,sizeof(instack)) ; // memset(sum,0,sizeof(sum)) ; } int N ; int judge(){ for(int i=1;i<=N;i++){ if(belong[i]==belong[i+N]) return 0 ; } return 1 ; } int main(){ int m ,a1, a2, c1, c2 ,wife_A ,wife_B ,hus_A ,hus_B; while(scanf("%d%d",&N,&m)!=EOF){ init() ; while(m--){ scanf("%d%d%d%d",&a1,&a2,&c1,&c2) ; a1++ ; a2++ ; wife_A=a1 ; hus_A=a1+N ; wife_B=a2 ; hus_B=a2+N ; if(c1==0&&c2==0){ add_edge(wife_A,hus_B) ; add_edge(wife_B,hus_A) ; } else if(c1==0&&c2==1){ add_edge(wife_A,wife_A) ; add_edge(hus_B,hus_A) ; } else if(c1==1&&c2==0){ add_edge(hus_A,hus_B) ; add_edge(wife_B,wife_A) ; } else if(c1==1&&c2==1){ add_edge(hus_A,wife_B) ; add_edge(hus_B,wife_A) ; } } for(int i=1;i<=2*N;i++){ if(dfn[i]==-1) tarjan(i) ; } printf("%s ",judge()==1?"YES":"NO") ; } return 0 ; }