1179: [Apio2009]Atm
Time Limit: 15 Sec Memory Limit: 162 MBSubmit: 1629 Solved: 615
[Submit][Status]
Description
Input
第一行包含两个整数N、M。N表示路口的个数，M表示道路条数。接下来M行，每行两个整数，这两个整数都在1到N之间，第i+1行的两个整数表示第i条道路的起点和终点的路口编号。接下来N行，每行一个整数，按顺序表示每个路口处的ATM机中的钱数。接下来一行包含两个整数S、P，S表示市中心的编号，也就是出发的路口。P表示酒吧数目。接下来的一行中有P个整数，表示P个有酒吧的路口的编号
Output
输出一个整数，表示Banditji从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。
Sample Input
6 7
1 2
2 3
3 5
2 4
4 1
2 6
6 5
10
12
8
16
1 5
1 4
4
3
5
6
1 2
2 3
3 5
2 4
4 1
2 6
6 5
10
12
8
16
1 5
1 4
4
3
5
6
Sample Output
47
HINT
50%的输入保证N, M<=3000。所有的输入保证N, M<=500000。每个ATM机中可取的钱数为一个非负整数且不超过4000。输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。
Source
题解：其实就是个tarjan求出强连通分量，缩个点，然后直接BFS扫一遍就完事了。。。但是问题来了，莫名其妙的WA了好多次，弄到数据才发现原来tarjan爆栈了（HansBug：TT）。。。后来加了个{$M 1000000000,0,maxlongint}就没事啦么么哒（再次对C/C++党的无限栈空间表示严重鄙视TT）
1 /************************************************************** 2 Problem: 1179 3 User: HansBug 4 Language: Pascal 5 Result: Accepted 6 Time:10444 ms 7 Memory:54356 kb 8 ****************************************************************/ 9 10 {$M 1000000000,0,maxlongint} 11 type 12 point=^node; 13 node=record 14 g:longint; 15 next:point; 16 end; 17 art=array[0..1000000] of point; 18 var 19 i,j,k,l,m,n,h,t,ans,x,y:longint; 20 a,d:art; 21 p:point; 22 ss,s:array[0..1000000] of boolean; 23 low,dfn,f,b,c,e,g:array[0..1000000] of longint; 24 function min(x,y:longint):longint;inline; 25 begin 26 if x<y then min:=x else min:=y; 27 end; 28 function max(x,y:longint):longint;inline; 29 begin 30 if x>y then max:=x else max:=y; 31 end; 32 procedure add(var a:art;x,y:longint);INLINE; 33 var p:point; 34 begin 35 new(p); 36 p^.g:=y; 37 p^.next:=a[x]; 38 a[x]:=p; 39 end; 40 procedure tarjan(x:longint);inline; 41 var i,j,k:longint;p:point; 42 begin 43 inc(h);low[x]:=h;dfn[x]:=h; 44 inc(t);f[t]:=x;ss[x]:=true;s[x]:=true; 45 p:=a[x]; 46 while p<>nil do 47 begin 48 if s[p^.g]=false then 49 begin 50 tarjan(p^.g); 51 low[x]:=min(low[x],low[p^.g]); 52 end 53 else if ss[p^.g] then low[x]:=min(low[x],dfn[p^.g]); 54 p:=p^.next; 55 end; 56 if dfn[x]=low[x] then 57 begin 58 inc(ans); 59 while f[t+1]<>x do 60 begin 61 ss[f[t]]:=false; 62 b[f[t]]:=ans; 63 dec(t); 64 end; 65 end; 66 end; 67 procedure search(x:longint);inline; 68 var 69 p:point; 70 f,r,i,j,k:longint; 71 b:array[0..1000000] of longint; 72 begin 73 f:=1;r:=2; 74 b[1]:=x; 75 while f<r do 76 begin 77 p:=a[b[f]]; 78 while p<>nil do 79 begin 80 if (e[b[f]]+c[p^.g])>e[p^.g] then 81 begin 82 e[p^.g]:=e[b[f]]+c[p^.g]; 83 b[r]:=p^.g; 84 inc(r); 85 end; 86 p:=p^.next; 87 end; 88 inc(f); 89 end; 90 end; 91 begin 92 read(n,m); 93 for i:=1 to n do a[i]:=nil; 94 for i:=1 to m do 95 begin 96 read(j,k); 97 add(a,j,k); 98 end; 99 fillchar(s,sizeof(s),false); 100 fillchar(ss,sizeof(ss),false); 101 fillchar(f,sizeof(f),0); 102 fillchar(low,sizeof(low),0); 103 fillchar(dfn,sizeof(dfn),0); 104 fillchar(b,sizeof(b),0); 105 fillchar(c,sizeof(c),0); 106 107 for i:=1 to n do 108 read(g[i]); 109 read(x,m); 110 ans:=0;h:=0;t:=0; 111 tarjan(x); 112 x:=b[x]; 113 for i:=1 to n do d[i]:=a[i]; 114 for i:=1 to n do a[i]:=nil; 115 for i:=1 to n do c[b[i]]:=c[b[i]]+g[i]; 116 fillchar(s,sizeof(s),false); 117 for i:=1 to n do 118 begin 119 p:=d[i]; 120 while p<> nil do 121 begin 122 if b[i]<>b[p^.g] then add(a,b[i],b[p^.g]); 123 p:=p^.next; 124 end; 125 end; 126 127 fillchar(e,sizeof(e),0); 128 e[x]:=c[x]; 129 search(x);k:=0; 130 for i:=1 to m do 131 begin 132 read(j); 133 k:=max(k,e[b[j]]); 134 end; 135 writeln(k); 136 readln; 137 readln; 138 end.