bzoj 1179: [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

Sample Output

47

HINT

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

Source

额,刷水凑数...tarjan缩点后是一个DAG,然后就只求DAG最长路,可以直接spfa;至于酒吧的话就缩点的时候或一下即可

// MADE BY QT666 #include<cstdio> #include<algorithm> #include<vector> #include<iostream> #include<cstring> using namespace std; typedef long long ll; const int N=500050; int gi() { int x=0,flag=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) flag=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar(); return x*flag; } int head[N],nxt[N],to[N],v[N],zhan[N],fr[N],dfn[N],low[N],vis[N],tt,cnt,n,m,pd[N],check[N],tot,sum; int S,P,w[N],dis[N],q[N*20],ans; vector<int>p[N]; void tarjan(int x){ dfn[x]=low[x]=++tt;zhan[++sum]=x; vis[x]=1;int y; for(int i=head[x];i;i=nxt[i]){ y=to[i]; if(!dfn[y]){ tarjan(y); low[x]=min(low[x],low[y]); } else if(vis[y]) low[x]=min(low[x],dfn[y]); } if(low[x]==dfn[x]){ tot++; do { y=zhan[sum--]; vis[y]=0,w[tot]+=v[y]; pd[tot]|=check[y],fr[y]=tot; for(int i=head[y];i;i=nxt[i]) p[tot].push_back(to[i]); } while(y!=x); } } void spfa(){ q[0]=fr[S];dis[fr[S]]=w[fr[S]]; int t=0,sum=1; while(t<sum){ int now=q[t++]; for(int i=0;i<p[now].size();i++){ int y=fr[p[now][i]]; if(y!=now&&dis[y]<dis[now]+w[y]){ dis[y]=dis[now]+w[y]; q[sum++]=y; } } } } void lnk(int x,int y){to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt;} int main(){ n=gi(),m=gi(); for(int i=1;i<=m;i++){ int x=gi(),y=gi(); lnk(x,y); } for(int i=1;i<=n;i++) v[i]=gi(); S=gi(),P=gi(); for(int i=1;i<=P;i++){ int x=gi();check[x]=1; } tarjan(S);spfa(); for(int i=1;i<=tot;i++) if(pd[i]) ans=max(ans,dis[i]); printf("%d\n",ans); }

bzoj 1179: [Apio2009]Atm