HDOJ 3715 - Go Deeper 二分+2-sat判断

               题意:

                         有这么一个过程:

                 

go(int dep, int n, int m)
begin
output the value of dep.
if dep < m and x[a[dep]] + x[b[dep]] != c[dep] then go(dep + 1, n, m)
end

                          其中x[]的值为0或1...c[]的值为0或1或2....现在告诉a[],b[],c[]..问这个过程最深可能是多少？

               题解

                         看这个过程..实际上当在m层没办法下去了.更深的层肯定也到不了了...所以满足单调性...先读入a[],b[],c[]...再二分M...构图..2-sat..tarjan判断....

Program:

#include<iostream>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<stack>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define oo 1000000007
#define MAXN 50005<<1
#define MAXM 500005<<1
#define ll long long
using namespace std;
struct node
{
int y,next;
}line[MAXM];
int A[MAXN],B[MAXN],C[MAXN],Lnum,_next[MAXN],dfn[MAXN],low[MAXN],tp[MAXN],tpnum,DfsIndex;
bool instack[MAXN];
stack<int> mystack;
void addline(int x,int y)
{
line[++Lnum].next=_next[x],_next[x]=Lnum,line[Lnum].y=y;
}
void tarjan(int x)
{
mystack.push(x),instack[x]=true;
dfn[x]=low[x]=++DfsIndex;
for (int k=_next[x];k;k=line[k].next)
{
int y=line[k].y;
if (!dfn[y])
{
tarjan(y);
low[x]=min(low[x],low[y]);
}else
if (instack[y])
low[x]=min(low[x],dfn[y]);
}
if (low[x]==dfn[x])
{
tpnum++;
do
{
x=mystack.top();
mystack.pop();
tp[x]=tpnum;
instack[x]=false;
}while (low[x]!=dfn[x]);
}
}
bool _2sat(int N,int M)
{
int i;
Lnum=0;
memset(_next,0,sizeof(_next));
for (i=1;i<=M;i++)
{
int a=A[i],b=B[i],c=C[i];
if (!c) addline(a<<1,b<<1|1),addline(b<<1,a<<1|1);
else
if (c==1)
{
addline(a<<1,b<<1),addline(a<<1|1,b<<1|1);
addline(b<<1,a<<1),addline(b<<1|1,a<<1|1);
}
else
if (c==2) addline(a<<1|1,b<<1),addline(b<<1|1,a<<1);
}
while (!mystack.empty()) mystack.pop();
memset(dfn,0,sizeof(dfn));
memset(instack,false,sizeof(instack));
DfsIndex=tpnum=0;
for (i=0;i<(N<<1);i++)
if (!dfn[i]) tarjan(i);
for (i=0;i<N;i++)
if (tp[i<<1]==tp[i<<1|1]) return false;
return true;
}
int main()
{
int N,M,cases;
scanf("%d",&cases);
while (cases--)
{
scanf("%d%d",&N,&M);
for (int i=1;i<=M;i++) scanf("%d%d%d",&A[i],&B[i],&C[i]);
int l=0,r=M+1,mid;
while (r-l>1)
{
mid=l+r>>1;
if (_2sat(N,mid)) l=mid;
else r=mid;
}
printf("%d\n",l);
}
return 0;
}