首页 > 代码库 > HDU 3062:Party(2-SAT入门)

HDU 3062:Party(2-SAT入门)

http://acm.hdu.edu.cn/showproblem.php?pid=3062

题意:中文。

思路:裸的2-SAT。判断二元组的两个人是否在同一个强连通分量。

学习地址:http://www.cnblogs.com/ambition/archive/2011/07/30/2-sat.html

 1 #include <bits/stdc++.h> 2 using namespace std; 3 #define N 2010 4 struct Edge { 5     int u, v, nxt; 6 } edge[N*N*2]; 7 int head[N], tot, belong[N], num, dfn[N], low[N], vis[N], tid; 8 stack<int> sta; 9 10 void Add(int u, int v) {11     edge[tot] = (Edge) { u, v, head[u] }; head[u] = tot++;12 }13 14 void init() {15     memset(head, -1, sizeof(head));16     memset(vis, 0, sizeof(vis));17     memset(dfn, 0, sizeof(dfn));18     memset(low, 0, sizeof(low));19     tot = num = tid = 0;20     while(!sta.empty()) sta.pop();21 }22 23 void tarjan(int u) {24     dfn[u] = low[u] = ++tid;25     vis[u] = 1; sta.push(u);26     for(int i = head[u]; ~i; i = edge[i].nxt) {27         int v = edge[i].v;28         if(!dfn[v]) {29             tarjan(v);30             if(low[u] > low[v]) low[u] = low[v];31         } else if (vis[v]) {32             if(low[u] > dfn[v]) low[u] = dfn[v];33         }34     }35     if(low[u] == dfn[u]) {36         num++;37         while(true) {38             int x = sta.top(); sta.pop();39             belong[x] = num;40             vis[x] = 0;41             if(x == u) break;42         }43     }44 }45 46 int main() {47     int n, m;48     while(~scanf("%d", &n)) {49         scanf("%d", &m); init();50         for(int i = 0; i < m; i++) {51             int a, b, c, d;52             scanf("%d%d%d%d", &a, &b, &c, &d);53             Add(a * 2 + c, b * 2 + (d + 1) % 2);54             Add(b * 2 + d, a * 2 + (c + 1) % 2);55         }56         for(int i = 0; i < 2 * n; i++) if(!dfn[i]) tarjan(i);57         bool flag = 1;58         for(int i = 0; i < n; i++)59             if(belong[i*2] == belong[i*2+1]) flag = 0;60         if(flag) puts("YES");61         else puts("NO");62     }63     return 0;64 }

 

HDU 3062:Party(2-SAT入门)