首页 > 代码库 > POJ 3648-Wedding(2-SAT)
POJ 3648-Wedding(2-SAT)
题面很邪恶啊。。。
一对新人请n-1对夫妻吃饭,人们坐在一张桌子的两侧,每一对互为夫妻关系的人必须坐在桌子的两侧。而且有些人两两之间会存在“通奸”关系,通奸关系不仅在男女之间,同性之间也有。新娘对面不可以座有通奸关系的人。判断是否存在可行的排座方案,存在的话输出和新娘同一排的人。
因为新娘对面不可以做有通奸关系的人,也就是说2sat求出的一组可行解是新娘对面的。
如果u和v有通奸关系,就连边u->v‘,v->u‘。
有一点需要注意,就是要连一条边0->1
这样如果选了0就必须选1,那么就矛盾了,所以0一定不被选,选出来的就是新郎那一边的。很巧妙啊!
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;const int N = 1010;const int M = 100010;struct Edge { int from, to, next;} edge[M], edge2[M];int head[N];int cntE, cntE2;void addedge(int u, int v) { edge[cntE].from = u; edge[cntE].to = v; edge[cntE].next = head[u]; head[u] = cntE++;}void addedge2(int u, int v) { edge2[cntE2].from = u; edge2[cntE2].to = v; edge2[cntE2].next = head[u]; head[u] = cntE2++;}int dfn[N], low[N], idx;int stk[N], top;int in[N];int kind[N], cnt;void tarjan(int u){ dfn[u] = low[u] = ++idx; in[u] = true; stk[++top] = u; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]); else if (in[v]) low[u] = min(low[u], dfn[v]); } if (low[u] == dfn[u]) { ++cnt; while (1) { int v = stk[top--]; kind[v] = cnt; in[v] = false; if (v == u) break; } }}int opp[N], ind[N], col[N]; // 相对的点 入度 染色 col[]=1选择bool topsort(int n) // 序号从0开始{ for (int i = 0; i < 2*n; i += 2) { int k1 = kind[i]; int k2 = kind[i^1]; // 相对的两个的关系 //printf("%d %d %d %d\n", i, i^1, k1, k2); if (k1 == k2) return false; opp[k1] = k2; opp[k2] = k1; } memset(head, -1, sizeof head); int u, v; for (int i = 0; i < cntE; ++i) { u = edge[i].from, v = edge[i].to; if (kind[u] != kind[v]) { // 反向建图 addedge2(kind[v], kind[u]); ind[kind[u]]++; } } queue<int> q; for (int i = 1; i <= cnt; ++i) if (!ind[i]) q.push(i); while (q.size()) { u = q.front(); q.pop(); if (!col[u]) col[u] = 1, col[ opp[u] ] = -1; for (int i = head[u]; i != -1; i = edge2[i].next) if (--ind[edge2[i].to] == 0) q.push(edge2[i].to); } return true;}void init() { cntE = cntE2 = 0; memset(head, -1, sizeof head); memset(dfn, 0, sizeof dfn); memset(in, false, sizeof in); idx = top = cnt = 0; memset(ind, 0, sizeof ind); memset(col, 0, sizeof col);}int main() { int n, m; int u, v; while (scanf("%d%d", &n, &m) == 2) { if (n == 0 && m == 0)break; init(); while (m--) { //3h 7h char s1, s2; scanf("%d%c%d%c", &u, &s1, &v, &s2); u = s1==‘w‘ ? u*2 : u*2+1; v = s2==‘w‘ ? v*2 : v*2+1; if (!u || !v) continue; addedge(u, v^1); addedge(v, u^1); } addedge(0, 1); for (int i = 0; i < 2 * n; ++i) { if (!dfn[i]) tarjan(i); } if (topsort(n)) { for (int i = 1; i < n; i++) { if (col[ kind[2*i] ] == 1) printf("%dh", i); else printf("%dw", i); if (i < n - 1) printf(" "); else printf("\n"); } } else printf("bad luck\n"); } return 0;}
POJ 3648-Wedding(2-SAT)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。