首页 > 代码库 > 2-Sat问题
2-Sat问题
二分+2-Sat
判断是否可行
输出字典序最小的解
输出字典序可行解
其实这些都是小问题，最重要的是建图，请看论文。
特殊的建边方式，如果a b是一对，a必须选，那么就是b->a建边。
HDU 3062 Party
模板题
#include <iostream>#include <cstring>#include <cstdio>#include <cstdlib>#include <algorithm>using namespace std;#define LL long longstruct node{ int u,v,next;}edge[2001*1001];int t,scnt,top;int first[2001];int DFN[2001];int Low[2001];int Belong[2001];int in[2001],stack[2001];void CL(){ t = top = scnt = 0; memset(first,-1,sizeof(first)); memset(DFN,0,sizeof(DFN));}void add(int u,int v){ edge[t].u = u; edge[t].v = v; edge[t].next = first[u]; first[u] = t ++;}void Tarjan(int u){ int v,i; DFN[u] = Low[u] = ++ t; in[u] = 1; stack[top++] = u; for(i = first[u];i != -1;i = edge[i].next) { v = edge[i].v; if(!DFN[v]) { Tarjan(v); if(Low[u] > Low[v]) { Low[u] = Low[v]; } } else if(in[v] && Low[u] > DFN[v]) { Low[u] = DFN[v]; } } if(DFN[u] == Low[u]) { scnt ++; do { v = stack[--top]; in[v] = 0; Belong[v] = scnt; }while(u != v); }}int main(){ int n,m,a1,a2,c1,c2,i,u,v; while(scanf("%d%d",&n,&m)!=EOF) { CL(); for(i = 0;i < m;i ++) { scanf("%d%d%d%d",&a1,&a2,&c1,&c2); u = a1*2+c1; v = a2*2+c2; add(u,v^1); add(v,u^1); } for(i = 0;i < 2*n;i ++) { if(!DFN[i]) { Tarjan(i); } } for(i = 0;i < n;i ++) { if(Belong[2*i] == Belong[2*i+1]) break; } if(i == n) printf("YES\n"); else printf("NO\n"); } return 0;}
HDU 1814 Peaceful Commission
论文上的例题，输出字典序。
#include <iostream>#include <cstring>#include <cstdio>#include <cstdlib>#include <algorithm>using namespace std;#define LL long long#define N 8001int que[2*N];int flag[2*N];int first[2*N];int t,n,num;struct node{ int u,v,next;}edge[60001];void CL(){ t = 1; memset(first,-1,sizeof(first)); memset(flag,0,sizeof(flag));}void add(int u,int v){ edge[t].u = u; edge[t].v = v; edge[t].next = first[u]; first[u] = t ++;}int dfs(int x){ int i,v; if(flag[x] == 1) return 1; else if(flag[x] == 2) return 0; flag[x] = 1; flag[x^1] = 2; que[num++] = x; for(i = first[x];i != -1;i = edge[i].next) { v = edge[i].v; if(!dfs(v)) return 0; } return 1;}int judge(){ int i,j; for(i = 0;i < 2*n;i ++) { if(flag[i]) continue; num = 0; if(!dfs(i)) { for(j = 0;j < num;j ++) { flag[que[j]] = 0; flag[que[j]^1] = 0; } if(!dfs(i^1)) return 0; } } return 1;}int main(){ int m,u,v,i; while(scanf("%d%d",&n,&m)!=EOF) { CL(); for(i = 0;i < m;i ++) { scanf("%d%d",&u,&v); u --; v --; add(u,v^1); add(v,u^1); } if(judge()) { for(i = 0;i < 2*n;i ++) { if(flag[i] == 1) printf("%d\n",i+1); } } else { printf("NIE\n"); } } return 0;}
HDU 3648 Wedding
输出可行解。
#include <iostream>#include <cstring>#include <cstdio>#include <cstdlib>#include <queue>#include <algorithm>using namespace std;#define LL long longstruct node{ int u,v,next;}edge[100001],g[100001];int t,scnt,top,T;int first[2001];int DFN[2001];int op[2001];int Low[2001];int Belong[2001];int in[2001],stack[2001];int input[2001];int flag[2001];void CL(){ T = t = top = scnt = 0; memset(first,-1,sizeof(first)); memset(DFN,0,sizeof(DFN)); memset(flag,0,sizeof(flag));}void add(int u,int v){ edge[t].u = u; edge[t].v = v; edge[t].next = first[u]; first[u] = t ++;}void _add(int u,int v){ g[T].u = u; g[T].v = v; g[T].next = first[u]; first[u] = T ++;}void Tarjan(int u){ int v,i; DFN[u] = Low[u] = ++ t; in[u] = 1; stack[top++] = u; for(i = first[u];i != -1;i = edge[i].next) { v = edge[i].v; if(!DFN[v]) { Tarjan(v); if(Low[u] > Low[v]) { Low[u] = Low[v]; } } else if(in[v] && Low[u] > DFN[v]) { Low[u] = DFN[v]; } } if(DFN[u] == Low[u]) { scnt ++; do { v = stack[--top]; in[v] = 0; Belong[v] = scnt; }while(u != v); }}void tpsort(){ queue<int> que; memset(first,-1,sizeof(first)); int i,v,u; for(i = 0;i < t;i ++) { u = Belong[edge[i].u]; v = Belong[edge[i].v]; if(u != v) { _add(v,u); input[u] ++; } } for(i = 1;i <= scnt;i ++) { if(input[i] == 0) que.push(i); } while(!que.empty()) { u = que.front(); que.pop(); if(flag[u] == 0) { flag[u] = 1; flag[op[u]] = 2; } for(i = first[u];i != -1;i = g[i].next) { v = g[i].v; if(--input[v] == 0) que.push(v); } }}int main(){ int n,m,i,u,v; char s1,s2; while(scanf("%d%d%*c",&n,&m)!=EOF) { if(n == 0&&m == 0) break; CL(); for(i = 0;i < m;i ++) { scanf("%d%c%*c%d%c%*c",&u,&s1,&v,&s2); if(s1 == ‘w‘) u = u*2; else u = u*2 + 1; if(s2 == ‘w‘) v = v*2; else v = v*2 + 1; if(u != (v^1)) { add(u,v^1); add(v,u^1); } } add(0,1); for(i = 0;i < 2*n;i ++) { if(!DFN[i]) { Tarjan(i); } } for(i = 0;i < n;i ++) { if(Belong[2*i] == Belong[2*i+1]) break; op[Belong[2*i]] = Belong[2*i+1]; op[Belong[2*i+1]] = Belong[2*i]; } if(i != n) { printf("bad luck\n"); continue; } tpsort(); int z = 0; for(i = 0; i < 2*n; i++) { if(flag[Belong[i]] == 1 && i != 1) { if(z) printf(" "); z = 1; printf("%d", i/2); if(i%2 == 0) printf("h"); else printf("w"); } } printf("\n"); } return 0;}
2-Sat问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。