題干：

有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裸題。因為題干中說一對夫妻有且只有一個人參加聚會，所以符合元素和元素的非 的性質。所以如果說A和B有仇，那就A->b , B -> a這樣就好。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 3000 + 5; struct Edge {int v,ne; } e[5000005]; int n,m; int head[MAX],tot;//1~n代表妻子，n+1到2*n代表丈夫 void add(int u,int v) {e[++tot].v = v;e[tot].ne = head[u];head[u] = tot; } int DFN[MAX],LOW[MAX],col[MAX],vis[MAX],index,stk[MAX],scc,clk; void Tarjan(int x) {DFN[x] = LOW[x] = ++clk;vis[x] = 1;stk[++index] = x;for(int i = head[x]; ~i; i = e[i].ne) {int v = e[i].v;if(!DFN[v]) {Tarjan(v);LOW[x] = min(LOW[x],LOW[v]);}else if(vis[v]) LOW[x] = min(LOW[x],DFN[v]);}if(LOW[x] == DFN[x]) {scc++;while(1) {int tmp = stk[index--];col[tmp] = scc;vis[tmp] = 0;if(tmp == x) break;}} } void init(int n) {tot=0;clk=index=scc=0;for(int i = 1; i<=2*n; i++) head[i] = -1,DFN[i]=LOW[i]=vis[i]=col[i]=0; } int main() {while(~scanf("%d%d",&n,&m)) {init(n);for(int c1,c2,a1,a2,i = 1; i<=m; i++) {scanf("%d%d%d%d",&a1,&a2,&c1,&c2);a1++,a2++;int U = a1 + c1*n,u=a1+(1-c1)*n;int V = a2 + c2*n,v=a2+(1-c2)*n;add(U,v);add(V,u); }for(int i = 1; i<=2*n; i++) {if(!DFN[i]) Tarjan(i);}int flag = 1;for(int i = 1; i<=n; i++) {if(col[i] == col[i+n]) {flag = 0;break;}}if(flag) puts("YES");else puts("NO");}return 0 ; } //20:10-20:39

總結：

當然對于這一題還有另一種建圖方式：鏈接

對于這道題，我們首先要虛擬節點，對于編號為i的妻子a和丈夫b，做法如下： （我用!來表示非，畢竟那些符號不好辦）

對妻子a： 對應的a虛擬為 節點 i ，對應的!a虛擬為節點 i + 2*N，?
對丈夫b： 對應的b虛擬為節點i + N ，!b虛擬為節點 i + N + 2*N。 這樣的話我們得到了4*N -1個節點。

由題意有以下建邊方案

一：夫妻a,b只能去一人且必須去一人。 得布爾表達式 (!a -> b)合取(!b -> a)合取(b -> !a)合取(a -> !b)

二：有矛盾的兩人不能同時去，這就意味著可能都不去。 得布爾表達式 (a -> !b)合取(b -> !a)

總結

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

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