bzoj1194

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

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<ctime>
  5 #include<cmath>
  6 #include<iostream>
  7 #include<algorithm>
  8 #include<queue>
  9 #include<stack>
 10 #include<set>
 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<int,int> 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<pii>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<int>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
",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 }

View Code

1194: [HNOI2006]潘多拉的盒子

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 255 Solved: 133
[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

Sample Output

HINT

Source

[Submit][Status][Discuss]