Bzoj1179 [apio2009]atm

Posted by yjjr's blog on February 6, 2018

标签:SPFA,tarjan缩点

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的单向的道路到达其中的至少一个酒吧。

 

算法很简单

Tarjan缩点重构图后跑一遍SPFA最长路就可以了

但是代码实现很复杂,很多细节,容易写挂题

SPFA中的初始点S,一定要赋值为belong[s]

剩下最短路中的,因为重构图,所以可以直接指向节点本身

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#ifdef WIN32
#define LL "%I64d\n"
#else
#define LL "%lld\n"
#endif
using namespace std;
inline ll read()
{
    ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxm=5e5+6,maxn=5e5+6;
int inq[maxn],que[maxn<<1],dfn[maxn],c[maxn],low[maxn],dis[maxn],v[maxn],tim=0,cnt=0,tot=0,top=0;
int last[maxn],rlast[maxn],belong[maxn];
int n,m,s,p;
struct edge{int to,next;}e[maxm<<1],re[maxm<<1];
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define ov e[i].to
#define newreg(x) for(int i=rlast[x];i;i=re[i].next)
#define rv re[i].to

void tarjan(int x)
{
	int now=0;
	dfn[x]=low[x]=++tim;
	que[++top]=x;inq[x]=1;
	reg(x)
	    if(!dfn[ov]){tarjan(ov);low[x]=min(low[x],low[ov]);}
	    else if(inq[ov])low[x]=min(low[x],dfn[ov]);
	if(low[x]==dfn[x]){
		tot++;
		while(now!=x){
			now=que[top--];
			belong[now]=tot;
			v[tot]+=c[now];
			inq[now]=0;
		}
	}
}
void rebuild()
{
	cnt=0;
	rep(k,1,n)
	    reg(k)
	        if(belong[k]!=belong[ov]){
			    re[++cnt]=(edge){belong[k],rlast[belong[ov]]};rlast[belong[ov]]=cnt;
				//re[++cnt]=(edge){belong[ov],rlast[belong[k]]};rlast[belong[k]]=cnt;
			}
}

void spfa()
{
	int head=1,tail=1;
	que[head]=belong[s];inq[belong[s]]=1;dis[belong[s]]=v[belong[s]];
	while(head<=tail){
		int now=que[head++];
		newreg(now)
			if(dis[now]+v[rv]>dis[rv]){
				dis[rv]=dis[now]+v[rv];
				if(!inq[rv]){
					inq[rv]=1;
					que[++tail]=rv;
				}
			}
		inq[now]=0;
	}
}
	
			
int main()
{
	n=read(),m=read();
	rep(i,1,m){
		int x=read(),y=read();
		e[++cnt]=(edge){x,last[y]};last[y]=cnt;
		//e[++cnt]=(edge){y,last[x]};last[x]=cnt;
	}
	rep(i,1,n)c[i]=read();
	rep(i,1,n)if(!dfn[i])tarjan(i);
	s=read(),p=read();
	rebuild();
	spfa();
	int ans=0;
	rep(i,1,p){
		int x=read();
		ans=max(ans,dis[belong[x]]);
	}
	cout<<ans<<endl;
	return 0;
}



本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr