「BZOJ1194」[HNOI2006] 潘多拉的盒子
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
题解
我们要追随PoPoQQQ大爷
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;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; } bool flag; int S,n,m,a,b; int last[55],last2[55]; int ind,scc,top,cnt,cnt2; int dfn[55],low[55],q[55],bl[55],val[55],ans[55]; bool inq[55],mark[55][55]; struct data{ int a[55][2]; bool danger[55]; }T[55]; struct edge{ int from,to,next; }e[10005],ed[10005]; 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; ed[++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]); } bool check()//a>b? { flag=0; memset(mark,0,sizeof(mark)); dfs(1,1); return !flag; } void tarjan(int x) { dfn[x]=low[x]=++ind; q[++top]=x;inq[x]=1; for(int i=last[x];i;i=e[i].next) if(!dfn[e[i].to]) tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]); else if(inq[e[i].to]) low[x]=min(low[x],dfn[e[i].to]); if(low[x]==dfn[x]) { int now=-1;scc++; while(now!=x) { now=q[top--];inq[now]=0; bl[now]=scc;val[scc]++; } } } int dfs(int x) { if(ans[x])return ans[x]; ans[x]=val[x]; for(int i=last2[x];i;i=ed[i].next) ans[x]=max(ans[x],dfs(ed[i].to)+val[x]); return ans[x]; } int main() { S=read(); for(int i=1;i<=S;i++) { n=read();m=read(); while(m--)T[i].danger[read()+1]=1; for(int j=1;j<=n;j++) T[i].a[j][0]=read()+1,T[i].a[j][1]=read()+1; } for(int i=1;i<=S;i++) for(int j=1;j<=S;j++) if(i!=j) { a=i;b=j; if(check())insert(a,b); } for(int i=1;i<=S;i++)if(!dfn[i])tarjan(i); for(int i=1;i<=cnt;i++) insert2(bl[e[i].from],bl[e[i].to]); int mx=0; for(int i=1;i<=scc;i++)mx=max(mx,dfs(i)); printf("%d\n",mx); return 0; } |
Subscribe
计数器 9855306
OI 课件=>
OI 课件=>