「BZOJ1179」[Apio2009] 抢掠计划atm
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的单向的道路到达其中的至少一个酒吧。
题解
直接上个tarjan缩完点spfa解决
|
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 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #define inf 0x7fffffff #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,S,p,tim,scc,top,cnt,ans; int head[500005],h[500005],f[500005]; int belong[500005],v[500005]; int c[500005],dfn[500005],low[500005],q[500005]; bool inq[500005]; struct data{int to,next;}e[500005]; struct edge{int to,next;}ed[500005]; void insert(int u,int v) {e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;} void ins(int u,int v) {ed[++cnt].to=v;ed[cnt].next=h[u];h[u]=cnt;} void tarjan(int x) { int now=0; dfn[x]=low[x]=++tim; q[++top]=x;inq[x]=1; for(int i=head[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]) { scc++; while(now!=x) { now=q[top];top--; belong[now]=scc; v[scc]+=c[now]; inq[now]=0; } } } void rebuild() { cnt=0; for(int i=1;i<=n;i++) for(int j=head[i];j;j=e[j].next) if(belong[i]!=belong[e[j].to]) ins(belong[i],belong[e[j].to]); } void spfa() { int t=0,w=1; q[t]=belong[S];inq[belong[S]]=1; f[belong[S]]=v[belong[S]]; while(t!=w) { int now=q[t];t++;if(t==500000)t=0; for(int i=h[now];i;i=ed[i].next) { if(f[now]+v[ed[i].to]>f[ed[i].to]) { f[ed[i].to]=f[now]+v[ed[i].to]; if(!inq[ed[i].to]) {inq[ed[i].to]=1;q[w++]=ed[i].to;if(w==500000)w=0;} } } inq[now]=0; } } int main() { n=read();m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(); insert(u,v); } for(int i=1;i<=n;i++) c[i]=read(); for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i); S=read();p=read(); rebuild(); spfa(); for(int i=1;i<=p;i++) { int x=read(); if(f[belong[x]]>ans)ans=f[belong[x]]; } printf("%d",ans); return 0; } |
Subscribe
计数器 9854577
OI 课件=>
OI 课件=>