洛谷2321 [hnoi2006]潘多拉的宝盒

tarjan缩点求最长链

Posted by yjjr's blog on October 31, 2018

标签:Tarjan缩点,bfs

题目

题目传送门

给定一些自动机,如果某个自动机A能产生的所有串都能在自动机B中产生,则称B是A的一个升级,求最长链

分析

两两连边,tarjan缩点求最长链

bfs判断A的所有串能否都在B中产生

具体分析参考PoPoQQQ大爷

blog

code

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
//**********head by yjjr**********
const int maxn=66;
bool flag;
int S,n,m,a,b,last[maxn],last2[maxn],tim=0,scc=0,top=0,cnt=0,cnt2=0;
int dfn[maxn],low[maxn],que[maxn],bl[maxn],val[maxn],ans[maxn];
bool inque[maxn],mark[maxn][maxn];
struct data{int a[maxn][2];bool danger[maxn];}T[maxn];
struct edge{int from,to,next;}e[100006],e2[100006]; 
void insert(int u,int v){e[++cnt]=(edge){u,v,last[u]};last[u]=cnt;}
void insert2(int u,int v){
	if(u==v)return;
	e2[++cnt2]=(edge){u,v,last2[u]};last2[u]=cnt2;
}
void dfs(int x,int y){
	if(flag)return;
	if(mark[x][y])return;mark[x][y]=1;
	if(T[b].danger[y]&&!T[a].danger[x]){flag=1;return;}
	dfs(T[a].a[x][0],T[b].a[y][0]);
	dfs(T[a].a[x][1],T[b].a[y][1]);
}
inline bool check(){
	flag=0;
	mem(mark,0);
	dfs(1,1);
	return !flag;
}
void tarjan(int x){
	dfn[x]=low[x]=++tim;
	que[++top]=x;inque[x]=1;
	reg(x){
		int v=e[i].to;
		if(!dfn[v])tarjan(v),low[x]=min(low[x],low[v]);
		else if(inque[v])low[x]=min(low[x],dfn[v]);
	}
	if(low[x]==dfn[x]){
		int now=-1;scc++;
		while(now!=x){
			now=que[top--];inque[now]=0;
			bl[now]=scc;val[scc]++;
		}
	}
}
inline int dfs(int x){
#define reg2(x) for(int i=last2[x];i;i=e2[i].next)
	if(ans[x])return ans[x];
	ans[x]=val[x];
	reg2(x)ans[x]=max(ans[x],dfs(e2[i].to)+val[x]);
	return ans[x];
} 
int main()
{
	S=read();
	rep(i,1,S){
		n=read(),m=read();
		while(m--)T[i].danger[read()+1]=1;
		rep(j,1,n)T[i].a[j][0]=read()+1,T[i].a[j][1]=read()+1;
	}
	rep(i,1,S)rep(j,1,S)
		if(i!=j){
			a=i,b=j;
			if(check())insert(a,b);
		}
	rep(i,1,S)if(!dfn[i])tarjan(i);
	rep(i,1,cnt)insert2(bl[e[i].from],bl[e[i].to]);
	int mx=0;
	rep(i,1,scc)mx=max(mx,dfs(i));
	cout<<mx<<endl;
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr