记录编号	410048	评测结果	AAAAAAAAAA
题目名称	[APIO2009] 抢掠计划	最终得分	100
用户昵称	皓芷	是否通过	通过
代码语言	C++	运行时间	0.173 s
提交时间	2017-05-30 21:16:49	内存使用	44.18 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
#include<vector>
#include<set>
#include<queue>
#define mysister //scc是强连通分量的缩写 
#define maxn 500001
using namespace std;
int n,m,s,p,vis[maxn],u,v,colour[maxn],cnt=0,w[maxn],sccw[maxn],d[maxn],ans=0;//定义详见代码 
vector<int>son[maxn];//正图 
vector<int>fa[maxn];//逆图 
vector<int>scc[maxn];//每个scc里的点 
set<int>sccto[maxn];//标号为i的scc所连出去的指向其他scc的边 
vector<int>b[maxn];//新图 
vector<int>bar;
stack<int>sta;//kosaraju第一遍df退出序 
queue<int>q;
void dfs_1(int u)
{
	vis[u]=1;
	for(int i=0;i<son[u].size();i++)if(!vis[son[u][i]])
	  dfs_1(son[u][i]);
	sta.push(u);
}
void dfs_2(int u)
{
	vis[u]=1;
	colour[u]=cnt;sccw[cnt]+=w[u];
	scc[cnt].push_back(u);
	for(int i=0;i<fa[u].size();i++)if(!vis[fa[u][i]])
	  dfs_2(fa[u][i]);
}
void spfa()
{
	memset(d,0,sizeof(d));
	memset(vis,0,sizeof(vis));
	int u=colour[s];
	q.push(u);
	d[u]=sccw[u];
	vis[u]=1;
	while(!q.empty())
	{
	  int u=q.front();q.pop();
	  for(int i=0;i<b[u].size();i++)if(d[b[u][i]]<d[u]+sccw[b[u][i]])
	  {
		d[b[u][i]]=d[u]+sccw[b[u][i]];
		if(!vis[b[u][i]]){q.push(b[u][i]);vis[b[u][i]]=1;}
	  }
	  vis[u]=0;
	}
}
int main()
{
	freopen("atm.in","r",stdin);
	freopen("atm.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
	{
	  scanf("%d%d",&u,&v);
	  son[u].push_back(v);
	  fa[v].push_back(u);
	}
	for(int i=1;i<=n;i++)
	  scanf("%d",&w[i]);
	scanf("%d%d",&s,&p);
	for(int i=0;i<p;i++)
	{
	  int o;
	  scanf("%d",&o);
	  bar.push_back(o);
	}
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
	  if(!vis[i])dfs_1(i);
	memset(vis,0,sizeof(vis));
	while(!sta.empty())
	{
	  if(!vis[sta.top()]){cnt++;dfs_2(sta.top());}
	  sta.pop();
	}
	for(int i=1;i<=cnt;i++)
	  for(int j=0;j<scc[i].size();j++)
	    for(int k=0;k<son[scc[i][j]].size();k++)
	  {
		if(!sccto[i].count(colour[son[scc[i][j]][k]])&&colour[son[scc[i][j]][k]]!=i)
		{
		  b[i].push_back(colour[son[scc[i][j]][k]]);
		  sccto[i].insert(colour[son[scc[i][j]][k]]);
		}
	  }
	spfa();
/*	for(int i=1;i<=cnt;i++){
	  for(int j=0;j<b[i].size();j++)
	    printf("%d->%d ",i,b[i][j]);
	    printf("\n");
	}*/
	for(int i=0;i<bar.size();i++)
	  ans=max(ans,d[colour[bar[i]]]);
	printf("%d",ans);
	return 0;
}