題目:

有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

Output

如果存在一種情況 則輸出YES
否則輸出 NO

Sample Input

2
1
0 1 1 1

Sample Output

YES

分析

2-sat詳解:https://blog.csdn.net/zeng_jun_yv/article/details/105316871
一道2—SAT的模板題，其實就是建立一個無向圖，然后求強連通分量，再看看同一對夫妻是不是在同一個強連通分量里。由對稱性解2-SAT問題

AC代碼：

/*由對稱性解2-SAT問題*/ #include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <stack> #include<algorithm> using namespace std; const int N = 2010; vector<int> vec[N]; int n, m, id, cnt; int dfn[N], vis[N], low[N], belong[N]; stack<int> s; void init() {memset(vis,0,sizeof(vis));memset(dfn,-1,sizeof(dfn));memset(low,-1,sizeof(low));memset(belong,-1,sizeof(belong));id = cnt = 0;while(!s.empty())s.pop();for(int i = 0; i < 2*n; i++)vec[i].clear(); } void tarjan(int u) {dfn[u] = low[u] = id++;vis[u] = 1;int sz = vec[u].size();s.push(u);for(int i = 0; i < sz; i++){int v = vec[u][i];if(dfn[v] == -1){tarjan(v);low[u] = min(low[u], low[v]);}else if(vis[v] == 1){low[u] = min(low[u], dfn[v]);}}if(low[u] == dfn[u]){cnt++;while(!s.empty()){int temp = s.top();s.pop();vis[temp]=0;belong[temp]=cnt;if(temp == u)break;}} } int main() {int a,b,c,d;while(~scanf("%d%d", &n, &m)){init();for(int i = 0; i < m; i++){scanf("%d%d%d%d", &a, &b, &c, &d);vec[2*a+c].push_back(2*b+1-d);vec[2*b+d].push_back(2*a+1-c);}for(int i = 0; i < 2*n; i++){if(dfn[i] == -1)tarjan(i);}bool flag = true;for(int i = 0; i < n; i++){if( belong[2*i] == belong[2*i+1] ){flag=false;break;}}puts(flag?"YES":"NO");}return 0; }

Tarjan+縮點+拓撲+染色

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std ; #define M 4000017 #define N 100017 //a<<1 和 (a<<1) + 1。a<<1表示妻子，(a<<1) + 1表示丈夫 //連接某邊是為了推出矛盾。x->y表示選x則必須選y //注意方向 struct node {int s, t;int nxt; } e[M]; int n, m; int idx, ans, tp, cont; int dfn[N],vis[N],low[N],head[N],st[N],belong[N];void add(int s,int t) {e[cont].s = s;e[cont].t = t;e[cont].nxt = head[s];head[s] = cont++; } void build_grap(int a, int b, int c, int d)//建圖 {if(c==0 && d==0)//兩個妻子{add(a<<1, (b<<1)+1);add(b<<1, (a<<1) + 1);}else if(c==0 && d==1)//妻子和丈夫{add((a<<1), (b<<1));add((b<<1)+1, (a<<1)+1);}else if(c==1 && d==0)//丈夫和妻子{add((a<<1) + 1, (b<<1) + 1);add(b<<1, a<<1);}else if(c==1 && d==1)//兩個丈夫有矛盾{add((a<<1)+1, b<<1);add((b<<1)+1, a<<1);} } void tarjan(int u) {dfn[u] = low[u] = ++idx;vis[u] = 1;st[++tp] = u;int v ;for(int i = head[u]; i != -1; i = e[i].nxt){v = e[i].t ;if(!dfn[v]){tarjan(v) ;low[u] = min(low[u],low[v]);}else if(vis[v])low[u] = min(low[u],dfn[v]);}if(dfn[u] == low[u]){ans++;while(1){v = st[tp--];vis[v] = 0;belong[v] = ans;if(v == u)break;}} } bool _2sat() {memset(vis,0,sizeof(vis));memset(dfn,0,sizeof(dfn));idx = tp = ans = 0;for(int i = 0; i < 2*n; i++)if(!dfn[i])tarjan(i) ;for(int i = 0; i < n; i++)if(belong[2*i]==belong[(2*i)^1])//矛盾return false ;return true; }int main() {int a, b, c, d;while(~scanf("%d%d",&n,&m)){cont = 0;memset(head,-1,sizeof(head));for(int i = 0; i < m; i++){scanf("%d%d%d%d",&a,&b,&c,&d);//int u, v;//u = a*2+c; v = b*2+d;//add(u, v^1); add(v, u^1);build_grap(a, b, c, d);}if(_2sat())printf("YES\n");elseprintf("NO\n");}return 0 ; } /**思路：每對夫妻代表圖中一個結點，只有 1、0 兩種選擇，對于有矛盾的夫妻對，使其不列席，讓無矛盾夫妻對的列席即可 對于 m 矛盾關系，設 a、b 兩對夫婦存在矛盾： 若第 a 對的妻子與第 b 對的妻子有矛盾（a b 0 0） 則 a 的妻子去了 b 的丈夫必須去，b 的妻子去了 a 的丈夫必須去：<a,0,b,1>、<b,0,a,1>，添邊：<a+n,b>,<b+n,a> 若第 a 對的妻子與第 b 對的丈夫有矛盾（a b 0 1） 則 a 的妻子去了 b 的妻子必須去，b 的丈夫去了 a 的丈夫必須去：<a,0,b,0>、<b,1,a,1>，添邊：<a+n,b+n>,<b,a> 若第 a 對的丈夫與第 b 對的妻子有矛盾（a b 1 0） 則 a 的丈夫去了 b 的丈夫必須去，b 的妻子去了 a 的妻子必須去：<a,1,b,1>、<b,0,a,0,>，添邊：<a,b>,<b+n,a+n> 若第 a 對的丈夫與第 b 對的丈夫有矛盾（a b 1 1） 則 a 的丈夫去了 b 的妻子必須去，b 的丈夫去了 a 的妻子必須去：<a,1,b,0>、<b,1,a,0>，添邊：<a,b+n>,<b,a+n>*/ #include<iostream> #include<cstdio> #include<stack> #include<cstring> #include<algorithm> using namespace std; const int N = 1e6+10; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std; struct node {int to,next; } node[N*2]; int head[N],tot; int n,m; int dfn[N],low[N]; bool vis[N];//標記數組 int scc[N];//記錄結點i屬于哪個強連通分量 int block_cnt;//時間戳 int sig;//記錄強連通分量個數 stack<int> S; void init() {tot=0;sig=0;block_cnt=0;memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(scc,0,sizeof(scc)); } void addnode(int from,int to) {node[++tot].to=to;node[tot].next=head[from];head[from]=tot; } void Tarjan(int x) {vis[x]=true;dfn[x]=low[x]=++block_cnt;//每找到一個新點，紀錄當前節點的時間戳S.push(x);//當前結點入棧for(int i=head[x]; i!=-1; i=node[i].next) //遍歷整個棧{int y=node[i].to;//當前結點的下一結點if(!dfn[y]){Tarjan(y);low[x]=min(low[x],low[y]);}else if(vis[y])low[x]=min(low[x],dfn[y]);}if(dfn[x]==low[x]) //滿足強連通分量要求{sig++;//記錄強連通分量個數while(true) //記錄元素屬于第幾個強連通分量{int temp=S.top();S.pop();vis[temp]=false;scc[temp]=sig;if(temp==x)break;}} } bool twoSAT() {for(int i=1; i<=2*n; i++) //找強連通分量if(!dfn[i])Tarjan(i);for(int i=1; i<=n; i++)if(scc[i]==scc[i+n])//條件a與!a屬于同一連通分量，無解return false;return true; } int main() {while( scanf("%d%d",&n,&m)!=EOF&&(n+m)){init();while(m--){int x,y,xVal,yVal;scanf("%d%d%d%d",&x,&y,&xVal,&yVal);x++;y++;if(xVal==0&&yVal==0) //x為0或y為0{addnode(x+n,y);//x為0,y為1addnode(y+n,x);//y為0,x為1}else if(xVal==0&&yVal==1) //x為0或y為1{addnode(x+n,y+n);//x為0,y為0addnode(y,x);//y為1,x為1}else if(xVal==1&&yVal==0) //x為1或y為0{addnode(x,y);//x為1,y為1addnode(y+n,x+n);//y為0,x為0}else if(xVal==1&&yVal==1) //x為1或y為1{addnode(x,y+n);//x為1,y為0addnode(y,x+n);//y為1,x為0}}bool flag=twoSAT();if(!flag)printf("NO\n");elseprintf("YES\n");}return 0; }

總結

以上是生活随笔為你收集整理的HDU 3062 Party（2-sat题模板+tarjan ）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。