[BZOJ1194][HNOI2006][强连通分量Tarjan+dfs]潘多拉的盒子

[BZOJ1194][HNOI2006]潘多拉的盒子

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

Sample Output

题目大意：咒语机中的元件每个都有两种情况，即把信号处理后把信号传给两个对应的元件，若信号传给了输出元件，那么就可以得到一个种类的信号。设每个咒语机可以产生若干种信号，那么找到一个最长上升序列使得序列中的每一个咒语机都能生成他之前每一个咒语机能生成的信号。

大概思路：我们可以先枚举两个咒语机之间的关系（比如咒语机a产生的信号种类数比咒语机b产生的信号种类数多），即让两个咒语机都一直向添加1移动或一直向添加0移动，若某个咒语机搜索时先遇到输出机，那么这个咒语机产生的信号种类一定比另一个多。枚举时按照a属于b的关系建立单向边。然后Tarjan缩点找最长链即可。

AC代码：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 using namespace std;
  5 int S,a,b,f,cnt,dfs_num,CN,top,re_cnt,maxn=0;
  6 int pre[6000],dye[6000],DFN[6000],LOW[6000],size[6000],in_tow[6000],tow[6000],re_pre[6000],ans[6000];
  7 int print[600][600],jdg[600][600];
  8 int move[600][600][2];
  9 struct pack{int from,to,next;} E[6000],re_E[6000];
 10 void add_edge(int x,int y){
 11     E[++cnt].to=y;
 12     E[cnt].next=pre[x];
 13     E[cnt].from=x;
 14     pre[x]=cnt;
 15 }
 16 void rebuild(){
 17     for(int i=1;i<=S;++i)
 18         for(int j=pre[i];j;j=E[j].next)
 19             if(dye[i]!=dye[E[j].to]){
 20                 re_E[++re_cnt].to=dye[E[j].to];
 21                 re_E[re_cnt].next=re_pre[dye[i]];
 22                 re_E[re_cnt].from=dye[i];
 23                 re_pre[dye[i]]=re_cnt;
 24         }
 25 }
 26 void dfs(int p,int q){
 27     if(jdg[p][q]||f) return ;
 28     jdg[p][q]=1;
 29     if(print[b][q]&&!print[a][p]) {f=1;return ;}
 30     dfs(move[a][p][0],move[b][q][0]);
 31     dfs(move[a][p][1],move[b][q][1]);
 32 }
 33 int check(){
 34     f=0;memset(jdg,0,sizeof(jdg));
 35     dfs(1,1);
 36     return !f;
 37 }
 38 void tarjan(int pos){
 39     DFN[pos]=LOW[pos]=++dfs_num;
 40     in_tow[tow[++top]=pos]=1;
 41     for(int i=pre[pos];i;i=E[i].next){
 42         if(!DFN[E[i].to]){
 43             tarjan(E[i].to);
 44             LOW[pos]=min(LOW[pos],LOW[E[i].to]);
 45         }
 46         else if(in_tow[E[i].to])
 47             LOW[pos]=min(LOW[pos],DFN[E[i].to]);
 48     }
 49     if(DFN[pos]==LOW[pos]){
 50         in_tow[pos]=0;
 51         size[dye[pos]=++CN]++;
 52         while(pos!=tow[top]){
 53             size[dye[tow[top]]=CN]++;
 54             in_tow[tow[top--]]=0;
 55         }
 56         --top;
 57     }
 58 }
 59 int req(int v){
 60     if(ans[v]) return ans[v];
 61     ans[v]=size[v];
 62     for(int i=re_pre[v];i;i=re_E[i].next)
 63         ans[v]=max(ans[v],req(re_E[i].to)+size[v]);
 64     return ans[v];
 65 }
 66 int find_max(){
 67     for(int i=1;i<=CN;++i) maxn=max(maxn,req(i));
 68     return maxn;
 69 }
 70 int main(){
 71     scanf("%d",&S);
 72     for(int i=1;i<=S;++i){
 73         int n,m;
 74         scanf("%d%d",&n,&m);
 75         for(int j=1;j<=m;++j){
 76             int t;
 77             scanf("%d",&t);
 78             print[i][t+1]=1;
 79         }
 80         for(int j=1;j<=n;++j){
 81             int t,tt;
 82             scanf("%d%d",&t,&tt);
 83             move[i][j][0]=t+1;
 84             move[i][j][1]=tt+1;
 85         }
 86     }
 87     for(int i=1;i<=S;++i)
 88         for(int j=1;j<=S;++j)
 89             if(i!=j){
 90                 a=i;
 91                 b=j;
 92                 if(check()) add_edge(i,j);
 93             }
 94     for(int i=1;i<=S;++i)
 95         if(!dye[i]) 
 96             tarjan(i);
 97     rebuild();
 98     printf("%d",find_max());
 99     return 0;
100 }