HDU3715(二分+2-SAT)

题意就是求满足题目中给出的递归代码的最大递归层数。

由于x[i]只有0和1，所以我们就比较容易想到2-SAT，然后二分递归层数，求出满足要求的最大递归层数。建图的时候，不满足不等式的就是互相矛盾的，然后建边。

#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <map>
#include <queue>
#include <stack>
#include <set>
#define M 40500
#define LL long long
#define Ld __int64
#define eps 0.00001
#define INF 999999999
#define MOD 112233
#define MAX 26
using namespace std;

vector<int> G[M];
int dfn[M],low[M],sccno[M],scc_cnt;
int indx;
stack<int> s;

void Tarjan(int u)
{
	indx++;
	dfn[u]=low[u]=indx;
	s.push(u);
	for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i];
		if(!dfn[v])
		{
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(!sccno[v])
		{
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(low[u]==dfn[u])
	{
		scc_cnt++;
		for(;;)
		{
			int x=s.top();
			s.pop();
			sccno[x]=scc_cnt;
			if(x==u)
				break;
		}
	}
}

void find_scc(int n)
{
	indx=scc_cnt=0;
	memset(dfn,0,sizeof(dfn));
	memset(sccno,0,sizeof(sccno));
	for(int i=0;i<n;i++)
		if(!dfn[i])
			Tarjan(i);
}
	
int a[M],b[M],c[M];

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=0;i<m;i++)
		{
			scanf("%d%d%d",&a[i],&b[i],&c[i]);
		}
		int l=0,r=m+1;
		while(l<r)
		{
			for(int i=0;i<n*2;i++)
				G[i].clear();
			int mid=(l+r)>>1;
			for(int i=0;i<mid;i++)
			{
				int k=a[i]<<1;
				int p=b[i]<<1;
				if(c[i]==0)					//至少有一个为1
				{
					G[k].push_back(p^1);	//k为0时，p^1一定为1
					G[p].push_back(k^1);
				}
				else if(c[i]==1)			//全为0或全为1
				{
					G[k].push_back(p);
					G[p].push_back(k);
					G[k^1].push_back(p^1);
					G[p^1].push_back(k^1);
				}
				else						//最多有一个为1
				{
					G[k^1].push_back(p);	//k^1为1时，p一定为0
					G[p^1].push_back(k);
				}
			}
			find_scc(n*2);
			int flag=0;
			for(int i=0;i<n*2;i+=2)
			{
				if(sccno[i]==sccno[i^1])
				{
					flag=1;
					break;
				}
			}
			if(flag)
			{
				r=mid;
			}
			else
			{
				l=mid+1;
			}
		}
		printf("%d\n",r-1);
	}
	return 0;
}

HDU3715(二分+2-SAT),布布扣,bubuko.com

HDU3715(二分+2-SAT)

原文：http://blog.csdn.net/mfmy_szw/article/details/24866269