O(S²)枚举2个诅咒机, 然后O(n²)BFS去判断. 构成一个有向图, tarjan缩点, 然后就是求DAG的最长路——题解来自lsj

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
                10 #include
               
                 11 #define clr(a,x) memset(a,x,sizeof(a)) 12 #define rep(i,l,r) for(int i=(l);i<(r);i++) 13 using namespace std; 14 typedef long long ll; 15 typedef pair
                
                  pii; 16 #define mkp(a,b) make_pair(a,b) 17 int read(){ 18 int ans=0,f=1; 19 char c=getchar(); 20 while(!isdigit(c)){ 21 if(c=='-') f=-1; 22 c=getchar(); 23 } 24 while(isdigit(c)){ 25 ans=ans*10+c-'0'; 26 c=getchar(); 27 } 28 return ans*f; 29 } 30 const int maxs=59,maxn=59,maxm=59; 31 struct edge{ 32 int v; 33 edge*next; 34 }e[maxn*maxn],*fir[maxn],*pt=e,E[maxn*maxn],*Fir[maxn],*Pt=E; 35 void addedge(int u,int v){ 36 pt->v=v;pt->next=fir[u]; 37 fir[u]=pt++; 38 } 39 void Addedge(int u,int v){ 40 Pt->v=v;Pt->next=Fir[u]; 41 Fir[u]=Pt++; 42 } 43 int s,n[maxs],m[maxs],v[maxs][maxn][2]; 44 bool vis[maxn][maxn],f[maxs][maxn]; 45 bool bfs(int x,int y){ 46 queue
                 
                  Q;Q.push(mkp(0,0)); 47 clr(vis,0); 48 while(!Q.empty()){ 49 int a=Q.front().first,b=Q.front().second;Q.pop(); 50 rep(i,0,2){ 51 int U=v[x][a][i],V=v[y][b][i]; 52 if(vis[U][V]) continue; 53 if(f[x][U]&&!f[y][V]) return 0; 54 Q.push(mkp(U,V));vis[U][V]=1; 55 } 56 } 57 return 1; 58 } 59 int ans,dfstime,scccnt,size[maxn],pre[maxn],low[maxn],scc[maxn]; 60 stack
                  
                   S; 61 void dfs(int x){ 62 pre[x]=low[x]=++dfstime;S.push(x); 63 for(edge*e=fir[x];e;e=e->next){ 64 if(!pre[e->v]){ 65 dfs(e->v); 66 low[x]=min(low[x],low[e->v]); 67 }else if(!scc[e->v]) low[x]=min(low[x],pre[e->v]); 68 } 69 if(pre[x]==low[x]){ 70 int t=-1;++scccnt; 71 while(t!=x){ 72 t=S.top();S.pop(); 73 scc[t]=scccnt;size[scccnt]++; 74 } 75 } 76 } 77 void tarjan(){ 78 rep(i,0,s) if(!scc[i]) dfs(i); 79 clr(vis,0); 80 rep(i,0,s){ 81 for(edge*e=fir[i];e;e=e->next){ 82 if(scc[i]!=scc[e->v]&&!vis[scc[i]][scc[e->v]]){ 83 vis[scc[i]][scc[e->v]]=1;Addedge(scc[i],scc[e->v]); 84 } 85 } 86 } 87 } 88 bool in[maxn]; 89 int w[maxn]; 90 void dp(int x){ 91 if(w[x]) return; 92 for(edge*e=Fir[x];e;e=e->next){ 93 dp(e->v);w[x]=max(w[x],w[e->v]); 94 } 95 w[x]+=size[x]; 96 } 97 void solve(){ 98 tarjan(); 99 rep(i,1,scccnt+1){100 for(edge*e=Fir[i];e;e=e->next) in[e->v]=1;101 }102 rep(i,1,scccnt+1) if(!in[i]) dp(i);103 rep(i,1,scccnt+1) ans=max(ans,w[i]);104 printf("%d\n",ans);105 }106 int main(){107 s=read();108 rep(i,0,s){109 n[i]=read();m[i]=read();110 rep(j,1,m[i]+1){111 int t=read();112 f[i][t]=1;113 }114 rep(j,0,n[i]){115 v[i][j][0]=read();v[i][j][1]=read();116 }117 }118 rep(i,0,s){119 rep(j,0,s) if(i!=j&&bfs(i,j)) addedge(i,j);120 }121 solve();122 return 0;123 }
                  
                 
                
               
              
             
            
           
          
         
        
       
      

1194: [HNOI2006]潘多拉的盒子

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 255  Solved: 133

[][][]

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

Sample Output

3

HINT

 

Source

 

[ ][ ][ ]