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

kk303 · · 1196 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

题意:

有这么一个过程:

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;
}

有疑问加站长微信联系（非本文作者）