Problem Description
小時候，鄉愁是一枚小小的郵票，我在這頭，母親在那頭。
????????????????????????—— 余光中

集訓是辛苦的，道路是坎坷的，休息還是必須的。經過一段時間的訓練，lcy決定讓大家回家放松一下，但是訓練還是得照常進行，lcy想出了如下回家規定，每一個隊（三人一隊）或者隊長留下或者其余兩名隊員同時留下；每一對隊員，如果隊員A留下，則隊員B必須回家休息下，或者B留下，A回家。由于今年集訓隊人數突破往年同期最高記錄，管理難度相當大，lcy也不知道自己的決定是否可行，所以這個難題就交給你了，呵呵，好處嘛~，免費**漂流一日。
?

Input
第一行有兩個整數，T和M，1<=T<=1000表示隊伍數，1<=M<=5000表示對數。
接下來有T行，每行三個整數，表示一個隊的隊員編號，第一個隊員就是該隊隊長。
然后有M行，每行兩個整數，表示一對隊員的編號。
每個隊員只屬于一個隊。隊員編號從0開始。
?

Output
可行輸出yes，否則輸出no，以EOF為結束。
?

Sample Input
1 2 0 1 2 0 1 1 2 2 4 0 1 2 3 4 5 0 3 0 4 1 3 1 4
?

Sample Output
yes no

（1）題目第一個條件：每一個隊或者隊長留下或者其與兩名隊員同時留下，或者表明只能為兩種情況中的一種；假設三人為A,B,C，隊長為A，0表示不留下，1表示留下，因為B與C同時留下或者不留下，只要B，C中其中一個沒有留下或者留下，則B,C中另一個也同樣留下或者不留下，所以可以從該條件中推導出六條等價關系，即A不留下->B，C同時留下，A留下->B，C同時不留下，B留下->C留下，A不留下，B留下->C留下，A不留下，C留下->B留下，A不留西，C不留下->B不留下，A留下；

（2）題目中第二個條件：每一對隊員，如果隊員A留下，則B必須回家休息，或者B留下，A必須回家休息；則可以推導出兩條等價式：A留下->B不留下，B留下->A不留下，注意在這個條件中可以A，B都不留下；

AC代碼：

#include <cstdio> #include <cstring> #include <queue> #include <vector> #include <stack> #include <algorithm> #include <iostream> #define MAXN 7000+10 #define MAXM 400000 #define INF 1000000 using namespace std; vector<int> G[MAXN]; int low[MAXN], dfn[MAXN]; int dfs_clock; int sccno[MAXN], scc_cnt; stack<int> S; bool Instack[MAXN]; int N, M; void init() {for(int i = 0; i <=6*N; i++) G[i].clear();while(S.size()) S.pop();dfs_clock=scc_cnt=0; } void getMap() {int a,b,c;for(int i=0;i<N;i++){scanf("%d %d %d",&a,&b,&c);G[a+N*3].push_back(b);G[a+N*3].push_back(c);G[b+3*N].push_back(a);G[c+3*N].push_back(a);}while(M--){scanf("%d%d",&a,&b);G[a].push_back(b+N*3);G[b].push_back(a+N*3);}} void tarjan(int u, int fa) {int v;low[u] = dfn[u] = ++dfs_clock;S.push(u);Instack[u] = true;for(int i = 0; i < G[u].size(); i++){v = G[u][i];if(!dfn[v]){tarjan(v, u);low[u] = min(low[u], low[v]);}else if(Instack[v])low[u] = min(low[u], dfn[v]);}if(low[u] == dfn[u]){scc_cnt++;for(;;){v = S.top(); S.pop();Instack[v] = false;sccno[v] = scc_cnt;if(v == u) break;}} } void find_cut(int l, int r) {memset(low, 0, sizeof(low));memset(dfn, 0, sizeof(dfn));memset(sccno, 0, sizeof(sccno));memset(Instack, false, sizeof(Instack));dfs_clock = scc_cnt = 0;for(int i = l; i <= r; i++)if(!dfn[i]) tarjan(i, -1); } void solve() {for(int i = 0; i < 3*N; i++){if(sccno[i] == sccno[i+3*N])//矛盾{printf("no\n");return ;}}printf("yes\n"); } int main() {while(scanf("%d%d", &N, &M) != EOF){init();getMap();find_cut(0, 6*N-1);solve();}return 0; }

?

總結

以上是生活随笔為你收集整理的图论--2-SAT--HDOJ/HDU 1824 Let's go home的全部內容，希望文章能夠幫你解決所遇到的問題。

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