hdu3715 二分+2sat+建图

题意：

给你一个递归公式，每多一层就多一个限制，问你最多能递归多少层。

思路：

先分析每一层的限制 x[a[i]] + x[b[i]] != c[i],这里面x[] = 0,1,c[i] = 0,1,2

如果我们把 x[]=0,1想成取或不取，就是基础的关系，那么这个题目就可以直接抽象成2sat问题，然后我们二分去枚举深度，每次根据2sat的结果判断二分走向，我的2sat用的是双深搜的强连通，用那个t打头的也行，随意，这样这个题目就ok了，对了下面总结下2sat的建图吧，这个题目也能用上。

#include<stdio.h>

#include<string.h>

#include<stack>

#define N_node 500 + 10

#define N_edge 100000 + 100



using namespace std;

typedef struct

{

   int to ,next;

}STAR;

STAR E1[N_edge] ,E2[N_edge];

int list1[N_node] ,list2[N_node] ,tot;

int Belong[N_node] ,cnt;

int mark[N_node];

int A[11000] ,B[11000] ,C[11000];

stack<int>st;

void add(int a ,int b)

{

   E1[++tot].to = b;

   E1[tot].next = list1[a];

   list1[a] = tot;

   E2[tot].to = a;

   E2[tot].next = list2[b];

   list2[b] = tot;

}

void DFS1(int s)

{

   mark[s] = 1;

   for(int k = list1[s] ;k ;k = E1[k].next)

   if(!mark[E1[k].to]) DFS1(E1[k].to);

   st.push(s);

}

void DFS2(int s)

{

   mark[s] = 1;

   Belong[s] = cnt;

   for(int k = list2[s] ;k ;k = E2[k].next)

   if(!mark[E2[k].to]) DFS2(E2[k].to);

}

bool ok(int mid ,int n)

{

   memset(list1 ,0 ,sizeof(list1));

   memset(list2 ,0 ,sizeof(list2));

   tot = 1;

   for(int i = 1 ;i <= mid ;i ++)

   {

      int x = A[i] * 2 ,xx = A[i] * 2 + 1;

      int y = B[i] * 2 ,yy = B[i] * 2 + 1;

      if(C[i] == 0) add(xx ,y) ,add(yy ,x);

      if(C[i] == 1) add(x ,y) ,add(y ,x) ,add(xx ,yy) ,add(yy ,xx);

      if(C[i] == 2) add(y ,xx) ,add(x ,yy);

   }

   memset(mark ,0 ,sizeof(mark));

   while(!st.empty()) st.pop();

   for(int i = 0 ;i < n * 2 ;i ++)

   if(!mark[i]) DFS1(i);

   memset(mark ,0 ,sizeof(mark));

   cnt = 0;

   while(!st.empty())

   {

      int xin = st.top();

      st.pop();

      if(mark[xin]) continue;

      cnt ++;

      DFS2(xin);

   }

   int mk = 0;

   for(int i = 0 ;i < n * 2 && !mk ;i += 2)

   if(Belong[i] == Belong[i^1]) mk = 1;

   return !mk;

}

int main ()

{

   int t ,n ,m ,i;

   scanf("%d" ,&t);

   while(t--)

   {

      scanf("%d %d" ,&n ,&m);

      for(i = 1 ;i <= m ;i ++)

      scanf("%d %d %d" ,&A[i] ,&B[i] ,&C[i]);

      int low ,mid ,up ,ans = 0;

      low = 0 ,up = m;

      while(low <= up)

      {

         mid = (low + up) >> 1;

         if(ok(mid ,n))

         ans = mid ,low = mid + 1;

         else up = mid - 1;

      }

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

   }

   return 0;

}

巴特西

hdu3715 二分+2sat+建图

最新文章

热门文章