1194: [HNOI2006]潘多拉的盒子
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 464 Solved: 221
[Submit][Status][Discuss]
Description
Input
第一行是一个正整数S，表示宝盒上咒语机的个数，（1≤S≤50）。文件以下分为S块，每一块描述一个咒语机，按照咒语机0,咒语机1„„咒语机S－1的顺序描述。每一块的格式如下。 一块的第一行有两个正整数n,m。分别表示该咒语机中元件的个数、咒语源输出元的个数（1≤m≤n≤50）。 接下来一行有m个数，表示m个咒语源输出元的标号（都在0到n-1之间）。接下来有n行，每一行两个数。第i行（0≤i≤n-1）的两个数表示pi,0和pi,1（当然，都在0到n-1之间）。
Output
第一行有一个正整数t,表示最长升级序列的长度。
Sample Input
4
1 1
0
0 0
2 1
0
1 1
0 0
3 1
0
1 1
2 2
0 0
4 1
0
1 1
2 2
3 3
0 0
1 1
0
0 0
2 1
0
1 1
0 0
3 1
0
1 1
2 2
0 0
4 1
0
1 1
2 2
3 3
0 0
Sample Output
3
HINT
Source
分析：
思路比较简单：对于每对i,j，如果满足i能产生的所有字符串j都能产生，则建边，跑最长路。
但是图可能不是DAG，所以要先预处理缩点，然后再做。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=;
struct data{int danger[N],lc[N],rc[N];}T[N];
struct edge{int v,next;}e[N*N*],e2[N*N*];
int S,ans,a,b,tot,head[N],tot2,head2[N];bool flag,vis[N][N];
int dfs_cnt,scc_cnt,top,dfn[N],low[N],num[N],sccno[N],stack[N],dp[N];
void add(int x,int y){
e[++tot].v=y;e[tot].next=head[x];head[x]=tot;
}
void add2(int x,int y){
e2[++tot2].v=y;e2[tot2].next=head2[x];head2[x]=tot2;
}
void dfs_contain(int x,int y){
if(vis[x][y]||flag) return ;
vis[x][y]=;
if(T[b].danger[y]&&!T[a].danger[x]){flag=;return ;}
dfs_contain(T[a].lc[x],T[b].lc[y]);
dfs_contain(T[a].rc[x],T[b].rc[y]);
}
bool check(int x,int y){
flag=;a=x;b=y;
memset(vis,,sizeof vis);
dfs_contain(,);
return !flag;
}
void tarjan(int u){
dfn[u]=low[u]=++dfs_cnt;
stack[++top]=u;
for(int i=head[u];i;i=e[i].next){
int v=e[i].v;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],dfn[v]);
}
else if(!sccno[v]){
low[u]=min(low[u],low[v]);
}
}
if(low[u]==dfn[u]){
scc_cnt++;
for(int x;;){
x=stack[top--];
sccno[x]=scc_cnt;
num[scc_cnt]++;//WA*2
if(x==u) break;
}
}
}
int get_cnt(int x){
if(dp[x]) return dp[x];
int maxn=num[x];//WA*1
for(int i=head2[x];i;i=e2[i].next){
maxn=max(maxn,dp[e2[i].v]+num[x]);
}
return dp[x]=maxn;
}
int main(){
scanf("%d",&S);
for(int k=,n,m,x,y;k<=S;k++){
scanf("%d%d",&n,&m);
while(m--) scanf("%d",&x),T[k].danger[x+]=;
for(int i=;i<=n;i++){
scanf("%d%d",&x,&y);
T[k].lc[i]=x+;
T[k].rc[i]=y+;
}
}
for(int i=;i<=S;i++){
for(int j=;j<=S;j++){
if(i==j) continue;
if(check(i,j)) add(i,j);
}
}
for(int i=;i<=S;i++) if(!dfn[i]) tarjan(i);
for(int i=;i<=S;i++){
for(int j=head[i];j;j=e[j].next){
if(sccno[i]!=sccno[e[j].v]) add2(sccno[i],sccno[e[j].v]);
}
}
for(int i=;i<=scc_cnt;i++) ans=max(ans,get_cnt(i));
printf("%d\n",ans);
return ;
}