wa on #3#11 87pts求助
查看原帖
wa on #3#11 87pts求助
194761
Isenthalpic楼主2020/12/19 13:14

拓扑,不知道哪里挂了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+10;
int pre[N],now[N],to[N],tot;
int n,m,p,s,top,num,cnt,col[N];
int sk[N],low[N],dfn[N],a[N];
int bar[N],f[N],in[N],out[N],siz[N],sum[N];
bool vis[N]; 
vector<int>scc[N],G[N];
queue<int>q;
void add(int x,int y){
	pre[++tot]=now[x];
	now[x]=tot;to[tot]=y;
}
void tarjan(int u){
	dfn[u]=low[u]=++num;
	vis[sk[++top]=u]=true;
	for(int i=now[u];i;i=pre[i]){
		int v=to[i];
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(vis[v])
			low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		int v;cnt++;
		do{
			
			v=sk[top--];
			scc[cnt].push_back(v);
			siz[cnt]++;
			sum[cnt]+=a[v];
			vis[v]=false;
			col[v]=cnt;
		}while(u!=v);
	}return;
}
void topsort(){
	f[col[s]]=sum[col[s]];
	q.push(col[s]);
	while(q.size()){
		int u=q.front();q.pop();
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i];
			f[v]=max(f[v],f[u]+sum[v]);
			if(!(--in[v]))q.push(v);
		}
	}
	return;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	scanf("%d%d",&s,&p);
	for(int i=1;i<=p;i++){
		int x;scanf("%d",&x);
		bar[x]=true;
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])tarjan(i);
	for(int u=1;u<=n;u++){
		for(int i=now[u];i;i=pre[i]){
			int v=to[i];
			if(col[v]==col[u])continue;
			G[col[u]].push_back(col[v]);
			in[col[v]]++;out[col[u]]++;
		}
	}
	memset(vis,0,sizeof(vis));
//	for(int i=1;i<=cnt;i++)f[i]=sum[i];
	topsort();
	int ans=0;
	int last=0;
	for(int i=1;i<=n;i++){
		if(!bar[i])continue;
		ans=max(ans,f[col[i]]);
	}
	printf("%d",ans);
	return 0;
}
2020/12/19 13:14
加载中...