BZOJ1179: [Apio2009]Atm

1179: [Apio2009]Atm

Time Limit: 15 Sec  Memory Limit: 162 MB
Submit: 1427  Solved: 544
[Submit][Status]

Description

BZOJ1179: [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
题解:
tarjan之后以scc[s]为起点做一遍spfa即可,若该scc内有酒吧则用它的d值更新答案
重构图的一种比较好的方法就是把所有的边记下来,tarjan之后可以memset(head,0,sizeof(head)),tot=0,重新insert
就不用在开其他的数组了,具体看代码
代码:
BZOJ1179: [Apio2009]Atm
 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<iostream>
 7 #include<vector>
 8 #include<map>
 9 #include<set>
10 #include<queue>
11 #define inf 1000000000
12 #define maxn 500000+10000
13 #define maxm 500+100
14 #define eps 1e-10
15 #define ll long long
16 using namespace std;
17 inline int read()
18 {
19     int x=0,f=1;char ch=getchar();
20     while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}
21     while(ch>=0&&ch<=9){x=10*x+ch-0;ch=getchar();}
22     return x*f;
23 }
24 int n,m,ss,p,cnt,tot,ti,top,head[maxn],low[maxn],dfn[maxn],scc[maxn];
25 int sta[maxn],from[maxn],go[maxn],q[2*maxn],a[maxn];
26 ll ans,s[maxn],d[maxn];
27 bool b[maxn],c[maxn],v[maxn];
28 
29 struct edge{int go,next;}e[maxn];
30 void insert(int x,int y)
31 {
32     e[++tot].go=y;e[tot].next=head[x];head[x]=tot;
33 }
34 void dfs(int x)
35 {
36     int y;
37     low[x]=dfn[x]=++ti;sta[++top]=x;
38     for(int i=head[x];i;i=e[i].next)
39      if (!dfn[y=e[i].go])
40       {
41           dfs(y);
42           low[x]=min(low[x],low[y]);
43       }
44      else if(!scc[y])low[x]=min(low[x],dfn[y]);
45     if(low[x]==dfn[x])
46     {
47         cnt++;
48         while(1)
49                  {
50                   scc[y=sta[top--]]=cnt;s[cnt]+=a[y];
51                   if(b[y])c[cnt]=1;
52                   if(y==x)break;
53                  }
54     }  
55 }
56 void tarjan()
57 {
58     for(int i=1;i<=n;i++)if(!dfn[i])dfs(i);
59 }
60 void spfa()
61 {
62     for(int i=1;i<=cnt;++i) d[i]=0;
63     memset(v,0,sizeof(v));
64     int l=0,r=1,x,y;q[1]=scc[ss];d[scc[ss]]=s[scc[ss]];
65     while(l!=r)
66     {
67         x=q[++l];if(l==maxn)l=0;v[x]=0;
68         for(int i=head[x];i;i=e[i].next)
69          if(d[x]+s[y=e[i].go]>d[y])
70          {
71              d[y]=d[x]+s[y];
72              if(!v[y]){v[y]=1;q[++r]=y;if(r==maxn)r=0;}
73          }
74     }
75 }
76 int main()
77 {
78     freopen("input.txt","r",stdin);
79     freopen("output.txt","w",stdout);
80     n=read();m=read();
81     int x,y;
82     for(int i=1;i<=m;i++)from[i]=read(),go[i]=read(),insert(from[i],go[i]);
83     for(int i=1;i<=n;i++)a[i]=read();
84     ss=read();p=read();
85     for(int i=1;i<=p;i++)x=read(),b[x]=1;
86     tarjan();
87     memset(head,0,sizeof(head));tot=0;
88     for(int i=1;i<=m;i++)
89      if(scc[x=from[i]]!=scc[y=go[i]])
90      {
91       insert(scc[x],scc[y]);
92      }
93     spfa();
94     ans=0;
95     for(int i=1;i<=cnt;i++)if(c[i])ans=max(ans,d[i]);
96     printf("%lld\n",ans);
97     return 0;
98 }
View Code

 


16
1 5
1 4
4
3
5
6

Sample Output

47

HINT

50%的输入保证N, M<=3000。所有的输入保证N, M<=500000。每个ATM机中可取的钱数为一个非负整数且不超过4000。输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。

Source

BZOJ1179: [Apio2009]Atm

上一篇:Ext JS学习第六天 Ext_window组件(三)


下一篇:ElasticSearch中Api学习汇总(46)