hdu3715 Go Deeper[二分+2-SAT]/poj2723 Get Luffy Out[二分+2-SAT]

这题转化一下题意就是给一堆形如$a_i + a_j e cquad (a_iin [0,1],cin [0,2])$的限制，问从开头开始最多到哪条限制全是有解的。

那么，首先有可二分性，所以直接二分枚举最大处，然后把这些限制加边做一次2-sat就好了。连边的话注意一下细节就行，$c=0$时候就是选$0$必须另一个选$1$，$c=1$是选同类，$c=2$就是选$1$另一个必须选$0$，然后注意一下$i=j$也就是对同一变量的特殊讨论，就是直接赋值型的连边。然后就没了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<queue>
 7 #define mst(x) memset(x,0,sizeof x)
 8 #define dbg(x) cerr << #x << " = " << x <<endl
 9 #define dbg2(x,y) cerr<< #x <<" = "<< x <<"  "<< #y <<" = "<< y <<endl
10 using namespace std;
11 typedef long long ll;
12 typedef double db;
13 typedef pair<int,int> pii;
14 template<typename T>inline T _min(T A,T B){return A<B?A:B;}
15 template<typename T>inline T _max(T A,T B){return A>B?A:B;}
16 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,1):0;}
17 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,1):0;}
18 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}
19 template<typename T>inline T read(T&x){
20     x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1;
21     while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x;
22 }
23 const int N=400+7,M=10000+7;
24 struct stothx{int x,y,c;}Q[M];
25 int n,m,T;
26 struct thxorz{
27     int head[N],to[M<<2],nxt[M<<2],dfn[N],low[N],tim,stk[N],instk[N],bel[N],Top,scc,tot;
28     inline void clear(){mst(head),mst(dfn),tot=tim=scc=0;}
29     inline void link(int x,int y){to[++tot]=y,nxt[tot]=head[x],head[x]=tot;}
30     void tarjan(int x){//dbg(x);
31         #define y to[j]
32         dfn[x]=low[x]=++tim,stk[++Top]=x,instk[x]=1;
33         for(register int j=head[x];j;j=nxt[j]){
34             if(!dfn[y])tarjan(y),MIN(low[x],low[y]);
35             else if(instk[y])MIN(low[x],dfn[y]);
36         }
37         if(dfn[x]==low[x]){
38             int tmp;++scc;
39             do instk[tmp=stk[Top--]]=0,bel[tmp]=scc;while(tmp^x);
40         }
41         #undef y
42     }
43     inline bool check(){
44         for(register int i=1;i<=n;++i)if(bel[i]==bel[i+n])return 0;
45         return 1;
46     }
47 }G;
48 inline bool check(int mid){//dbg(mid);
49     G.clear();
50     for(register int i=1;i<=mid;++i){
51         int x=Q[i].x,y=Q[i].y,c=Q[i].c;
52         if(x==y){
53             if(c==0)G.link(x,x+n);
54             else if(c==2)G.link(x+n,x);
55         }
56         else{
57             if(c==0)G.link(x,y+n),G.link(y,x+n);
58             else if(c==1)G.link(x,y),G.link(y,x),G.link(x+n,y+n),G.link(y+n,x+n);
59             else G.link(x+n,y),G.link(y+n,x);
60         }
61     }
62     for(register int i=1;i<=n<<1;++i)if(!G.dfn[i])G.tarjan(i);
63     return G.check();
64 }
65 
66 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);
67     read(T);while(T--){
68         read(n),read(m);
69         for(register int i=1;i<=m;++i)read(Q[i].x),read(Q[i].y),read(Q[i].c),++Q[i].x,++Q[i].y;
70         int L=0,R=m;
71         while(L<R){
72             int mid=L+R+1>>1;
73             if(check(mid))L=mid;
74             else R=mid-1;
75         }
76         printf("%d
",L);
77     }
78     return 0;
79 }

hdu3715

然后poj这题基本思路基本都是差不多，就是建边的时候花样变了一下，具体情况3类分析一下即可，同样注意特殊情况（同状态连边）要考虑到。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<queue>
 7 #define mst(x) memset(x,0,sizeof x)
 8 #define dbg(x) cerr << #x << " = " << x <<endl
 9 #define dbg2(x,y) cerr<< #x <<" = "<< x <<"  "<< #y <<" = "<< y <<endl
10 using namespace std;
11 typedef long long ll;
12 typedef double db;
13 typedef pair<int,int> pii;
14 template<typename T>inline T _min(T A,T B){return A<B?A:B;}
15 template<typename T>inline T _max(T A,T B){return A>B?A:B;}
16 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,1):0;}
17 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,1):0;}
18 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}
19 template<typename T>inline T read(T&x){
20     x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1;
21     while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x;
22 }
23 const int N=3000+7,M=3000+7;
24 struct stothx{int x,y,c;}Q[M];
25 int n,m,T;
26 struct thxorz{
27     int head[N],to[M<<1],nxt[M<<1],dfn[N],low[N],tim,stk[N],instk[N],bel[N],Top,scc,tot;
28     inline void clear(){mst(head),mst(dfn),tot=tim=scc=0;}
29     inline void link(int x,int y){to[++tot]=y,nxt[tot]=head[x],head[x]=tot;}
30     void tarjan(int x){//dbg(x);
31         #define y to[j]
32         dfn[x]=low[x]=++tim,stk[++Top]=x,instk[x]=1;
33         for(register int j=head[x];j;j=nxt[j]){
34             if(!dfn[y])tarjan(y),MIN(low[x],low[y]);
35             else if(instk[y])MIN(low[x],dfn[y]);
36         }
37         if(dfn[x]==low[x]){
38             int tmp;++scc;
39             do instk[tmp=stk[Top--]]=0,bel[tmp]=scc;while(tmp^x);
40         }
41         #undef y
42     }
43     inline bool check(){
44         for(register int i=1;i<=n;++i)if(bel[i]==bel[i+n])return 0;
45         return 1;
46     }
47 }G;
48 int bel[N],id[N],a[M],b[M];
49 inline bool check(int mid){//dbg(mid);
50     G.clear();
51     for(register int i=1;i<=mid;++i){
52         int x=bel[a[i]],y=bel[b[i]],xi=id[a[i]],yi=id[b[i]];
53         if(a[i]==b[i])xi?G.link(x,x+n):G.link(x+n,x);
54         else if(x^y)G.link(xi?x:x+n,yi?y+n:y),G.link(yi?y:y+n,xi?x+n:x);
55     }
56     for(register int i=1;i<=n<<1;++i)if(!G.dfn[i])G.tarjan(i);
57     return G.check();
58 }
59 
60 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);
61     while(read(n),read(m),n||m){
62         for(register int i=1,x,y;i<=n;++i){
63             read(x),read(y);
64             bel[x]=bel[y]=i,id[x]=0,id[y]=1;
65         }
66         for(register int i=1;i<=m;++i)read(a[i]),read(b[i]);
67         int L=0,R=m;
68         while(L<R){
69             int mid=L+R+1>>1;
70             if(check(mid))L=mid;
71             else R=mid-1;
72         }
73         printf("%d
",L);
74     }
75     return 0;
76 }

poj2723