51Nod 2840 ATM

Problem

Siruseri 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定， 在每个路口都设立了一个 Siruseri 银行的 ATM 取款机。令人奇怪的是，Siruseri 的酒吧也都设在路口，虽然并不是每个路口都设有酒吧。Banditji 计划实施 Siruseri 有史以来最惊天动地的 ATM 抢劫。他将从市中心 出发，沿着单向道路行驶，抢劫所有他途径的 ATM 机，最终他将在一个酒吧庆 祝他的胜利。使用高超的黑客技术，他获知了每个 ATM 机中可以掠取的现金数额。他希 望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可 以经过同一路口或道路任意多次。但只要他抢劫过某个 ATM 机后，该 ATM 机 里面就不会再有钱了。 例如，假设该城中有 6 个路口，道路的连接情况如下图所示： [没有图] 市中心在路口 1，由一个入口符号→来标识，那些有酒吧的路口用双圈来表示。每个 ATM 机中可取的钱数标在了路口的上方。在这个例子中，Banditji 能抢 劫的现金总数为 47，实施的抢劫路线是：1-2-4-1-2-3-5。

第一行包含两个整数N、M。N表示路口的个数，M表示道路条数。 接下来M行，每行两个整数，这两个整数都在1到N之间， 第i+1行的两个整数表示第i条道路的起点和终点的路口编号。 接下来N行，每行一个整数，按顺序表示每个路口处的ATM机中的钱数。 接下来一行包含两个整数S、P，S表示市中心的编号，也就是出发的路口。P表示酒吧数目。 接下来的一行中有P个整数，表示P个有酒吧的路口的编号 N, M<=500000。每个ATM机中可取的钱数为一个非负整数且不超过4000。 输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。

输出一个整数，表示Banditji从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。

n，m范围50W

Solution

Tarjan缩点，然后新图上跑拓扑。

Code

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAXN=500020;
const int MAXM=500020;
int n,m,idx,cnt,g[MAXN];
int dfn[MAXN],low[MAXN];
bool instack[MAXN];
struct E{
	int u,v,nex;
	bool operator<(const E x)const{
		if(u==x.u) return v<x.v;
		return u<x.u;
	}
	bool operator==(const E x)const{
		return u==x.u&&v==x.v&&nex==x.nex;
	}
}e[MAXM];
stack<int>s;
vector<int>belong[MAXN];
int p2p[MAXN];
void Tarjan(int u){
	dfn[u]=low[u]=++idx;
	s.push(u);
	instack[u]=true;
	for(int i=g[u];i>0;i=e[i].nex){
		int v=e[i].v;
		if(!dfn[v]){
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(instack[v]){
			low[u]=min(low[u],dfn[v]);
		}
	}
	if(dfn[u]==low[u]){
		++cnt;
		int cur;
		do{
			cur=s.top();s.pop();
			instack[cur]=false;
			belong[cnt].push_back(cur);
			p2p[cur]=cnt;
		}while(cur!=u);
	}
}
int money[MAXN];
int jiub[MAXN];
int st,num;
int nn;
int new_money[MAXN];
int dp[MAXN];
int du[MAXN];
void dfs(int u){
	//dp[u]=max(dp[u],sum+new_money[u]);
	for(int i=g[u];i>0;i=e[i].nex){
		int v=e[i].v;
		du[v]--;
		dp[v]=max(dp[v],dp[u]+new_money[v]);
		if(du[e[i].v]==0){
			dfs(e[i].v);
		}
	}
}
int main(){
	io_opt;
	cin>>n>>m;
	int x,y;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		e[i]=(E){x,y,g[x]};g[x]=i;
	}
	for(int i=1;i<=n;i++){
		cin>>money[i];
	}
	cin>>st>>num;
	for(int i=1;i<=num;i++){
		cin>>jiub[i];
	}
	Tarjan(st);
	for(int i=1;i<=m;i++){
		int u=e[i].u,v=e[i].v;
		if(!p2p[u]||!p2p[v]||p2p[u]==p2p[v]){
			e[i].u=e[i].v=1000000;
			e[i].nex=1000000;
		}
		else{
			e[i].u=p2p[u];
			e[i].v=p2p[v];
			e[i].nex=0;
		}
	}
	for(int i=1;i<=cnt;i++){
		for(int j=0;j<belong[i].size();j++){
			new_money[i]+=money[belong[i][j]];
			//cout<<belong[i][j]<<' ';
		}
		//cout<<endl;
	}
	sort(e+1,e+1+m);
	nn=unique(e+1,e+1+m)-(e+1);
	while(e[nn].nex==1000000) nn--;
	/*for(int i=1;i<=nn;i++){
		cout<<e[i].u<<' '<<e[i].v<<' '<<e[i].nex<<endl;
	}*/
	memset(g,0,sizeof(g));
	for(int i=1;i<=nn;i++){
		e[i].nex=g[e[i].u];
		g[e[i].u]=i;
		du[e[i].v]++;
	}
	//cout<<p2p[st]<<endl;
	/*for(int i=1;i<=nn;i++){
		cout<<e[i].u<<' '<<e[i].v<<endl;
	}*/
	dp[p2p[st]]=new_money[p2p[st]];
	dfs(p2p[st]);
	int ans=0;
	for(int i=1;i<=num;i++){
		ans=max(ans,dp[p2p[jiub[i]]]);
	}
	cout<<ans<<endl;
	return 0;
}