纠结死人的2-sat

分类: IT文章 • 2023-11-29 21:44:07

通用解法：

对于2-sat，一般而言有两种做法。做法一：直接for一遍未被选过的节点。假定当前节点为Ai，dfs判定及选定它的后代节点。若不满足，则再对Ai'进行此操作。做法二：先tarjan缩点判是否矛盾。然后拓扑排序自底向上输出答案。

关于自底向上算法的证明我觉得论文说得不是很清楚，在这里提一下。自底向上操作时，因为是拓扑排序后的序列，所以当选到某个点时，它的出度必然为零。既然出度为零，那么有三种可能：一是它没有后代节点，可以选；二是它的后代节点都被选完了，它可以选；第三种比较复杂，设当前节点未被遍历节点为Si，那么它没被选择的后代节点设为v。有一种不满足题意的情况是，选了Si，但是没有选择v。我们知道，v在拓扑序列中排在Si前面，如果v没被选择，那么v'被选择，而Si'是排在v'前面的，这就说明Si已经被遍历过，与前面假设矛盾。综上，不存在Si，它的后代节点没被选过。（这段话要结合算法来理解）前两种情况它都可以选，第三种情况不存在...证毕。（感觉这种做法好巧妙...我怎么就想不出这种算法...）

至此，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         else
64             for (int i=1;i<=nn;i++)
65                 if (color[i]==1) printf("%d
",i);
66     }
67     return 0;
68 }

//2-sat 0

poj 3678:

2-sat 好题。理解了2-sat之后，建图不是问题。

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <iostream>
 4 #define mp make_pair
 5 #define opp(v) (v<=n?v+n:v-n)
 6 using namespace std;
 7 const int maxn=1001<<1,maxm=1000001<<2;
 8 
 9 int ta[maxn],lin[maxm],sd[maxm],pos;
10 void biu(int s,int t) { ++pos; lin[pos]=ta[s]; ta[s]=pos; sd[pos]=t; }
11 
12 int set[maxn];
13 int fin(int d)
14 {
15     if (d==set[d]) return d;
16     return set[d]=fin(set[d]);
17 }
18 void uion(int x,int y) { set[x]=y; }
19 
20 int dfn[maxn],low[maxn],cnt;
21 int sta[maxn],spo;
22 bool vis[maxn];
23 void tarjan(int v)
24 {
25     dfn[v]=low[v]=++cnt;
26     sta[++spo]=v; vis[v]=1;
27 
28     for (int i=ta[v];i;i=lin[i])
29         if (!dfn[sd[i]])
30         {
31             tarjan(sd[i]);
32             low[v]=min(low[v],low[sd[i]]);
33         }
34         else if (vis[sd[i]]) low[v]=min(low[v],low[sd[i]]);
35     if (dfn[v]==low[v])
36         do
37         {
38             set[sta[spo]]=v;
39             vis[sta[spo]]=0;
40         } while (sta[spo--]!=v);
41 }
42 
43 int n,nn;
44 void init()
45 {
46     nn=n<<1;
47     pos=0; cnt=0;
48     for (int i=1;i<=nn;i++)
49     {
50         ta[i]=0;
51         dfn[i]=low[i]=0;
52         set[i]=i;
53     }
54     
55     int m;
56     scanf("%d",&m);
57     int a,b,c; char op[4];
58     while (m--)
59     {
60         scanf("%d%d%d%s",&a,&b,&c,op);
61         a++; b++;
62         if (op[0]=='A')
63         {
64             if (c) biu(a+n,a),biu(b+n,b);
65             else   biu(a,b+n),biu(b,a+n);
66         }
67         else if (op[0]=='O')
68         {
69             if (c) biu(a+n,b),biu(b+n,a);
70             else   biu(a,a+n),biu(b,b+n);
71         }
72         else
73         {
74             if (c) biu(a,b+n),biu(b,a+n),biu(a+n,b),biu(b+n,a);
75             else   biu(a,b),biu(b,a),biu(a+n,b+n),biu(b+n,a+n);
76         }
77     }
78 }
79 int main()
80 {
81     for (;scanf("%d",&n)!=EOF;)
82     {
83         init();
84         for (int i=1;i<=nn;i++) if (!dfn[i]) tarjan(i);
85         //for (int i=1;i<=nn;i++) cout<<i-1<<" "<<set[i]<<" "<<dfn[i]<<" "<<low[i]<<endl;
86         bool flag=1;
87         for (int i=1;i<=n;i++)
88             if (fin(i)==fin(i+n)) { flag=0; break; } //low[i]==low[i+n] -_-
89         printf("%s
",flag?"YES":"NO");
90     }
91     return 0;
92 }

//2-sat 1

小小感悟：

做了两道题了，也算是对2-sat有了一定的认识了。来说说我对2-sat的理解吧。

2-sat 中最重要的概念我认为是建图中的必要关系。比如两个点Si, Sj互斥，那么Si选了之后就必须选Sj'，Sj同理。只要了解这个建图的原理，poj 3678这种稍有变化的题对我们来说就不是难事了。

hdu 3622:

二分+2-sat判定。精度要到1e-4才行。我觉得是因为有可能r-l<1e-3，但l=1.0049,r=1.0051。具体解决方法就是把每次判断l和r所确定的端点值是否一样，不一样的话继续二分。不过这方法可行度不高...在做题的时候，尽量把eps定得低一些吧。（我觉得小3个数量级应该够了）

 1 //11639828    2014-09-12 08:49:10    Accepted    3622    343MS    616K    1735 B    G++    TofE
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <iostream>
 5 #define mp make_pair
 6 #define opp(v) ((v+1^1)-1)
 7 #define dbg(x) cout<<#x<<"="<<x<<endl
 8 using namespace std;
 9 const int maxn=101<<1,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 dfn[maxn],low[maxn],cnt;
15 int sta[maxn],spo;
16 bool vis[maxn];
17 int set[maxn];
18 void tarjan(int v)
19 {
20     dfn[v]=low[v]=++cnt;
21     sta[++spo]=v; vis[v]=1;
22 
23     for (int i=ta[v];i;i=lin[i])
24         if (!dfn[sd[i]])
25         {
26             tarjan(sd[i]);
27             low[v]=min(low[v],low[sd[i]]);
28         }
29         else if (vis[sd[i]]) low[v]=min(low[v],low[sd[i]]);
30     if (dfn[v]==low[v])
31         do
32         {
33             set[sta[spo]]=v;
34             vis[sta[spo]]=0;
35         } while (sta[spo--]!=v);
36 }
37 
38 struct pot{
39     double x,y;
40 }wu[maxn];
41 
42 int n,nn;
43 void init()
44 {
45     nn=n<<1;
46     for (int i=1;i<=nn;i+=2)
47         for (int j=0;j<2;j++)
48             scanf("%lf%lf",&wu[i+j].x,&wu[i+j].y);
49 }
50 bool co(int i,int j,double R)
51 {
52     if (4*R*R>(wu[i].x-wu[j].x)*(wu[i].x-wu[j].x)+(wu[i].y-wu[j].y)*(wu[i].y-wu[j].y)) return 1;
53     return 0;
54 }
55 bool judge(double R)
56 {
57     pos=0; cnt=0;
58     for (int i=1;i<=nn;i++)
59     {
60         ta[i]=dfn[i]=low[i]=0;
61         set[i]=i;
62     }
63     for (int i=1;i<=nn;i+=2)
64         for (int j=i+2;j<=nn;j++)
65         {
66             if (co(i,j,R))   biu(i,opp(j)),biu(j,opp(i));
67             if (co(i+1,j,R)) biu(i+1,opp(j)),biu(j,opp(i+1));
68         }
69     for (int i=1;i<=nn;i++) if (!dfn[i]) tarjan(i);
70     for (int i=1;i<=nn;i+=2) if (set[i]==set[i+1]) return 0;
71     return 1;
72 }
73 void solve()
74 {
75     double l=0,r=30000,mid;
76     while (r-l>=1e-4) //1e-3就会挂...
77     {
78         mid=(l+r)/2;
79         if (judge(mid)) l=mid;
80         else             r=mid;
81     }
82     printf("%.2f
",l);
83 }
84 int main()
85 {
86     for (;scanf("%d",&n)!=EOF;)
87     {
88         init();
89         solve();
90     }
91     return 0;
92 }

//2-sat 2

纠结死人的2-sat

相关推荐