记录编号	301964	评测结果	AWAAWAAAAA
题目名称	[APIO2009] 抢掠计划	最终得分	80
用户昵称	农场主	是否通过	未通过
代码语言	C++	运行时间	0.119 s
提交时间	2016-09-03 08:29:11	内存使用	24.63 MiB

#include<cstdio>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<algorithm>
#define maxn 500000
using namespace std;
vector<int> G[maxn];
vector<int> g[maxn];
int dp[maxn]={0},s,S,n,m,time=0,D[maxn]={0},d[maxn]={0},tot=0,dt[maxn]={0},low[maxn]={0},mp[maxn]={0};
bool T[maxn]={0},t[maxn]={0},vis[maxn]={0};
queue<int> q;
#define u mp[g[f][i]]
void spfa(){
	memset(vis,0,sizeof(vis));
	q.push(s);
	dp[s]=d[s];
	vis[s]=1;
	int ans=0;
	if (t[s]==1){
		ans=dp[s];
	}
	while(!q.empty()){
		int f=q.front();
		for (int i=0;i<g[f].size();i++) if(f!=u){
			if (dp[u]<dp[f]+d[u]){
				dp[u]=dp[f]+d[u];
				if (vis[u]==0){
					vis[u]=1;
					q.push(u);
				}
			}
		}
		vis[f]=0;
		//printf("%d %d\n",f,dp[f]);
		q.pop();
	}
	for (int i=1;i<=tot;i++){
		if (dp[i]>ans&&t[i]==1) ans=dp[i];
		//printf("");
	}
	printf("%d\n",ans);
}
stack<int> st;
void makenode(int x){
	tot++;
	while(0==st.empty()){
		int p=st.top();
		mp[p]=tot;
		d[tot]+=D[p];
		t[tot]=t[tot]|T[p];
		for (int i=0;i<G[p].size();i++){
			g[tot].push_back(G[p][i]);
			//printf("	%d %d\n",tot,G[p][i]);
		}
		vis[p]=1;
		st.pop();
		if (dt[x]==dt[p]){
			break;
		}
	}
	/*for (int i=0;i<g[tot].size();i++){
		printf("%d %d\n",tot,g[tot][i]);
	}*/
	//printf("	%d\n",t[tot]);
}
void dfs(int x){
	if (vis[x]!=0) return; 
	dt[x]=++time;
	low[x]=dt[x];
	st.push(x);
	for (int i=0;i<G[x].size();i++){
		if (low[G[x][i]]==0||low[x]<low[G[x][i]]){
			dfs(G[x][i]);
		}
		if (vis[G[x][i]]==0)low[x]=min(low[x],low[G[x][i]]);
	}
//	printf("%d %d %d\n",x,dt[x],low[x]);
	if (dt[x]==low[x]) makenode(x);
}
void read(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		G[a].push_back(b);
	}
	for (int i=1;i<=n;i++){
		scanf("%d",&D[i]);
	}
	int p;
	scanf("%d%d",&S,&p);
	for (int i=1;i<=p;i++){
		int o;
		scanf("%d",&o);
		T[o]=1;
	}
}
int main(){
	freopen("atm.in","r",stdin);
	freopen("atm.out","w",stdout);
	read();
	dfs(S);
	s=mp[S];
	spfa();
/*	for (int i=1;i<=tot;i++){
		for (int j=0;j<g[i].size();j++){
			printf("%d %d\n",i,g[i][j]);
		}
		printf("\n");
	}*/
}