首页 > 代码库 > 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入门)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。