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

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

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

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #define mst(x) memset(x,0,sizeof x)

 #define dbg(x) cerr << #x << " = " << x <<endl

 #define dbg2(x,y) cerr<< #x <<" = "<< x <<"  "<< #y <<" = "<< y <<endl

 using namespace std;

 typedef long long ll;

 typedef double db;

 typedef pair<int,int> pii;

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}

 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}

 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 const int N=+,M=+;

 struct stothx{int x,y,c;}Q[M];

 int n,m,T;

 struct thxorz{

     int head[N],to[M<<],nxt[M<<],dfn[N],low[N],tim,stk[N],instk[N],bel[N],Top,scc,tot;

     inline void clear(){mst(head),mst(dfn),tot=tim=scc=;}

     inline void link(int x,int y){to[++tot]=y,nxt[tot]=head[x],head[x]=tot;}

     void tarjan(int x){//dbg(x);

         #define y to[j]

         dfn[x]=low[x]=++tim,stk[++Top]=x,instk[x]=;

         for(register int j=head[x];j;j=nxt[j]){

             if(!dfn[y])tarjan(y),MIN(low[x],low[y]);

             else if(instk[y])MIN(low[x],dfn[y]);

         }

         if(dfn[x]==low[x]){

             int tmp;++scc;

             do instk[tmp=stk[Top--]]=,bel[tmp]=scc;while(tmp^x);

         }

         #undef y

     }

     inline bool check(){

         for(register int i=;i<=n;++i)if(bel[i]==bel[i+n])return ;

         return ;

     }

 }G;

 inline bool check(int mid){//dbg(mid);

     G.clear();

     for(register int i=;i<=mid;++i){

         int x=Q[i].x,y=Q[i].y,c=Q[i].c;

         if(x==y){

             if(c==)G.link(x,x+n);

             else if(c==)G.link(x+n,x);

         }

         else{

             if(c==)G.link(x,y+n),G.link(y,x+n);

             else if(c==)G.link(x,y),G.link(y,x),G.link(x+n,y+n),G.link(y+n,x+n);

             else G.link(x+n,y),G.link(y+n,x);

         }

     }

     for(register int i=;i<=n<<;++i)if(!G.dfn[i])G.tarjan(i);

     return G.check();

 }

 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);

     read(T);while(T--){

         read(n),read(m);

         for(register int i=;i<=m;++i)read(Q[i].x),read(Q[i].y),read(Q[i].c),++Q[i].x,++Q[i].y;

         int L=,R=m;

         while(L<R){

             int mid=L+R+>>;

             if(check(mid))L=mid;

             else R=mid-;

         }

         printf("%d\n",L);

     }

     return ;

 }

hdu3715

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

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #define mst(x) memset(x,0,sizeof x)

 #define dbg(x) cerr << #x << " = " << x <<endl

 #define dbg2(x,y) cerr<< #x <<" = "<< x <<"  "<< #y <<" = "<< y <<endl

 using namespace std;

 typedef long long ll;

 typedef double db;

 typedef pair<int,int> pii;

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}

 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}

 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 const int N=+,M=+;

 struct stothx{int x,y,c;}Q[M];

 int n,m,T;

 struct thxorz{

     int head[N],to[M<<],nxt[M<<],dfn[N],low[N],tim,stk[N],instk[N],bel[N],Top,scc,tot;

     inline void clear(){mst(head),mst(dfn),tot=tim=scc=;}

     inline void link(int x,int y){to[++tot]=y,nxt[tot]=head[x],head[x]=tot;}

     void tarjan(int x){//dbg(x);

         #define y to[j]

         dfn[x]=low[x]=++tim,stk[++Top]=x,instk[x]=;

         for(register int j=head[x];j;j=nxt[j]){

             if(!dfn[y])tarjan(y),MIN(low[x],low[y]);

             else if(instk[y])MIN(low[x],dfn[y]);

         }

         if(dfn[x]==low[x]){

             int tmp;++scc;

             do instk[tmp=stk[Top--]]=,bel[tmp]=scc;while(tmp^x);

         }

         #undef y

     }

     inline bool check(){

         for(register int i=;i<=n;++i)if(bel[i]==bel[i+n])return ;

         return ;

     }

 }G;

 int bel[N],id[N],a[M],b[M];

 inline bool check(int mid){//dbg(mid);

     G.clear();

     for(register int i=;i<=mid;++i){

         int x=bel[a[i]],y=bel[b[i]],xi=id[a[i]],yi=id[b[i]];

         if(a[i]==b[i])xi?G.link(x,x+n):G.link(x+n,x);

         else if(x^y)G.link(xi?x:x+n,yi?y+n:y),G.link(yi?y:y+n,xi?x+n:x);

     }

     for(register int i=;i<=n<<;++i)if(!G.dfn[i])G.tarjan(i);

     return G.check();

 }

 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);

     while(read(n),read(m),n||m){

         for(register int i=,x,y;i<=n;++i){

             read(x),read(y);

             bel[x]=bel[y]=i,id[x]=,id[y]=;

         }

         for(register int i=;i<=m;++i)read(a[i]),read(b[i]);

         int L=,R=m;

         while(L<R){

             int mid=L+R+>>;

             if(check(mid))L=mid;

             else R=mid-;

         }

         printf("%d\n",L);

     }

     return ;

 }

poj2723

巴特西

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

最新文章

热门文章