有n对夫妻被邀请参加一个聚会,因为场地的问题,每对夫妻中只有1人可以列席。在2n 个人中,某些人之间有着很大的矛盾(当然夫妻之间是没有矛盾的),有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席?
Inputn: 表示有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
Output如果存在一种情况 则输出YES
否则输出 NO
Sample Input
2 1 0 1 1 1
Sample Output
YES
该题用2-SAT算法
给出不同集合,求是否有满足条件的元素
https://blog.csdn.net/hawo11/article/details/74908233(sat浅析)
样例解释
0 1 1 1
是表示第0对和第1对的丈夫有矛盾,所以它们的妻子可以出席,输出YES
#include<cstdio> #include<cstring> #include<vector> using namespace std; const int maxn= 1000+10; struct TwoSAT { int n; vector<int> G[maxn*2]; int s[maxn*2],c; bool mark[maxn*2]; bool dfs(int x) { if(mark[x^1]) return false; if(mark[x]) return true; mark[x]=true; s[c++]=x; for(int i=0;i<G[x].size();i++) if(!dfs(G[x][i])) return false; return true; } void init(int n) { this->n=n; for(int i=0;i<n*2;i++) G[i].clear(); memset(mark,0,sizeof(mark)); } void add(int x,int xval,int y,int yval) { x=x*2+xval; y=y*2+yval; G[x].push_back(y); } bool solve() { for(int i=0;i<2*n;i+=2) if(!mark[i] && !mark[i+1]) { c=0; if(!dfs(i)) { while(c>0) mark[s[--c]]=false; if(!dfs(i+1)) return false; } } return true; } }TS; int main() { int n,m; while(scanf("%d%d",&n,&m)==2) { TS.init(n); while(m--) { int a,b,va,vb; scanf("%d%d%d%d",&a,&b,&va,&vb); TS.add(a,va,b,vb^1); TS.add(b,vb,a,va^1); } printf("%s\n",TS.solve()?"YES":"NO"); } return 0; }