首页 > 代码库 > 纠结死人的2-sat
纠结死人的2-sat
hdu 1814:
这道题是2-sat的模板题，比较基础…这题的输出方案比较棘手，说是拓扑排序用不了。
比较无语的是：这题用论文上的算法1是可以过的...
1 #include <cstdio> 2 #include <algorithm> 3 #include <stack> 4 #include <iostream> 5 #include <queue> 6 #define mp make_pair 7 #define opp(v) ((v+1^1)-1) 8 using namespace std; 9 const int maxn=16001,maxm=40001;10 11 int ta[maxn],lin[maxm],sd[maxm],pos;12 void biu(int s,int t) { ++pos; lin[pos]=ta[s]; ta[s]=pos; sd[pos]=t; }13 14 int n,nn;15 int color[maxn];16 void init()//--17 {18 pos=0;19 nn=n<<1;20 for (int i=1;i<=nn;i++)21 {22 ta[i]=0;23 color[i]=0;24 }25 }26 int jl[maxn],po;27 bool dfs(int v)28 {29 if (color[v]==1) return 1;30 if (color[v]==2) return 0;31 color[v]=1; color[opp(v)]=2;32 jl[++po]=v;33 bool flag=1;34 for (int i=ta[v];i;i=lin[i])35 if (!dfs(sd[i])) { flag=0; break; }36 return flag;37 }38 int main()39 {40 for (int m;scanf("%d%d",&n,&m)!=EOF;)41 {42 init();43 44 for (int a,b;m--;)45 {46 scanf("%d%d",&a,&b);47 if (a>b) swap(a,b);48 biu(a,(b+1^1)-1);49 biu(b,(a+1^1)-1);50 }51 bool flag=1;52 for (int v=1;v<=nn;v++)53 {54 if (color[v]) continue;55 po=0;56 if (!dfs(v))57 {58 do color[jl[po]]=color[opp(jl[po])]=0; while (--po);59 if (!dfs(opp(v))) { flag=0; break; }60 }61 }62 if (!flag) puts("NIE");63 else64 for (int i=1;i<=nn;i++)65 if (color[i]==1) printf("%d\n",i);66 }67 return 0;68 }
做了一道题之后，说说我对2-sat的理解吧。
对于2-sat，一般而言有两种做法。
做法一：直接for一遍未被选过的节点。假定当前节点为Ai，dfs判定及选定它的后代节点。若不满足，则再对Ai‘进行此操作。
做法二：先tarjan缩点判是否矛盾。然后拓扑排序自底向上输出答案。
关于自底向上算法的证明我觉得论文说得不是很清楚，在这里提一下。
自底向上操作时，因为是拓扑排序后的序列，所以当选到某个点时，它的出度必然为零。既然出度为零，那么只有两种可能：一是它没有后代节点，可以选；二是它的后代节点都被选完了，它可以选。两种情况它都可以选...证毕。（感觉这种做法好巧妙...我怎么就想不出这种算法...）
至此，2-sat的研究可以说是告一段落了。
（待续...）
纠结死人的2-sat
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。