蒟蒻求助(wa-1)
查看原帖
蒟蒻求助(wa-1)
113113
wuyuxuan2018楼主2020/12/12 21:21
#include<stack>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int NR=5e5+10;
const int MR=5e5+10;
struct edge
{
	int to,next;
};
int fte[NR],gsz;
edge g[MR];
void addedge(int x,int y)
{
	g[++gsz]=(edge){y,fte[x]};
	fte[x]=gsz;
}
int dfn[NR],low[NR],now=0;
int color,colsz[NR],col[NR];//大点的编号,大点内小点个数,染色的色。 
stack <int> s;
int n,m,h;
int cost[NR];
long long pay[NR],f[NR];
int dx[MR],dy[MR],in[NR],st;
bool bar[NR];
void tarjan(int x)
{
	s.push(x);
	dfn[x]=low[x]=++now;
	for(int i=fte[x];i;i=g[i].next)
	{
		int y=g[i].to;
		if(!dfn[y])
		{
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(!col[y])
		{
			low[x]=min(low[x],dfn[y]);
		}
	}
	if(dfn[x]==low[x])//成一个大点 
	{	
		color++;
		int t=0;
		while(s.top()!=x)
		{
			col[s.top()]=color;
			pay[color]+=cost[s.top()];
			s.pop();
			colsz[color]++;
		}
		col[s.top()]=color;
		pay[color]+=cost[s.top()];
		s.pop();
		colsz[color]++;
	}
}
void toposort()
{
	queue <int> q;
	for(int i=1;i<=color;i++)
	{
		if(in[i]==0)
		{
			q.push(i);
			f[i]=pay[i];
		 } 
	}
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(int i=fte[x];i;i=g[i].next)
		{
			int y=g[i].to;
			in[y]--;
			f[y]=max(f[y],f[x]);
			if(in[y]==0)
			{
				q.push(y);
				f[y]+=pay[y];
			} 
		}
	}
}
int main()
{	
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		addedge(x,y);
		dx[i]=x;
		dy[i]=y;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>cost[i];
	}
	for(int i=1;i<=n;i++)
	{
		if(!col[i]) tarjan(i);
	}
	cin>>st>>h;
	for(int i=1;i<=h;i++)
	{
		int x;
		cin>>x;
		bar[col[x]]=true;
	}
	gsz=0;
	memset(fte,0,sizeof(fte));
	for(int i=1;i<=m;i++)
	{
		if(col[dx[i]]!=col[dy[i]])
		{
			addedge(col[dx[i]],col[dy[i]]);
			in[col[dy[i]]]++;
		}
	}
	toposort();
	long long c=0;
	for(int i=1;i<=color;i++)
	{
		if(bar[i])
		{
			c=max(c,f[i]);
			//cout<<f[i]<<endl;
		}
	}
	cout<<c-f[col[st]]+pay[col[st]]<<endl;
	return 0;
}

Tarjan+toposort+DP

2020/12/12 21:21
加载中...