1179: [Apio2009]Atm

1179: [Apio2009]Atm

Time Limit: 15 Sec  Memory Limit: 162 MB
Submit: 1629  Solved: 615
[Submit][Status]

Description

1179: [Apio2009]Atm

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

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.

 

1179: [Apio2009]Atm

上一篇:win2008关闭增强安全配置


下一篇:Win8安装msi程序出现2502、2503错误解决方法