萌新刚学OI,缩点+topo求条(玄2关)
查看原帖
萌新刚学OI,缩点+topo求条(玄2关)
1250354
CP_2309楼主2024/7/25 11:01
#include <bits/stdc++.h>
using namespace std;
const int N=10010,M=100010;
struct node{int to,nex;}e[M],e2[M];
bool flag[N],vis[N];
int pos[N],sum,n,m,zzb,st[N],top,dt[N],dis[N],head[N],cnt,hd[N],ct,dfn[N],low[N],w[N],in[N],pc[N],s,p;
vector<int> v[N];
void add(int x, int y)
{
	e[++cnt].to=y;
	e[cnt].nex=head[x];
	head[x]=cnt;
}
void add2(int x,int y)
{
	e2[++ct].to=y;
	e2[ct].nex=hd[x];
	hd[x]=ct;
}
void tarjan(int x)
{
	low[x]=dfn[x]=++sum;
	vis[x]=1;
	st[++top]=x;
	for (int i=head[x];i;i=e[i].nex)
	{
		int y=e[i].to;
		if (!dfn[y])
		{
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if (vis[y])
		{
			low[x]=min(low[x],dfn[y]);
		}
	}
	if (dfn[x]==low[x])
	{
		zzb++;
		v[zzb].push_back(x);
		w[zzb]+=dt[x];
		while (top>0&&st[top]!=x)
		{
			int k=st[top];
			v[zzb].push_back(k);
			w[zzb]+=dt[k];
			pos[k]=zzb;
			vis[k]=0;
			top--;
		}
		top--;
		pos[x]=zzb;
		vis[x]=0;
	}
}
void topo_sort()
{
	queue<int>q;
	q.push(s);
	while (!q.empty())
	{
		int x=q.front();
		q.pop();
		for (int i=hd[x];i;i=e2[i].nex)
		{
			int y=e2[i].to;
			dis[y]=max(dis[y],dis[x]+w[y]); 
			in[y]--;
			if (in[y]==0)
			{
				q.push(y);
			} 
		}
	}
}
void init()
{
	cin >> n >> m;
	for (int i=1;i<=m;++i)
	{
		int x,y;
		cin >> x >> y;
		add(x,y);
	}
	for (int i=1;i<=n;++i)
	{
		cin >> dt[i];
	}
	cin >> s >> p;
	for (int i=1;i<=p;++i)
	{
		cin >> pc[i];
	}
}
signed main()
{
	init();
	for (int i = 1; i <= n; i++) 
	{
		if (!dfn[i]) 
		{
			tarjan(i);
		}
	}
	for (int i=1;i<=n;++i)
	{
		for (int j=head[i];j;j=e[j].nex)
		{
			int y=e[j].to;
			if (pos[i]!=pos[y])
			{
				add2(pos[i],pos[y]);
				in[pos[y]]++;
			}
		}
	}
	for (int i=1;i<=zzb;++i)
	{
		dis[i]=w[i];
	}
	topo_sort();
	int ans=0;
	for (int i=1;i<=p;++i)
	{
		cerr << dis[pos[pc[i]]] << ' ';
		ans=max(ans,dis[pos[pc[i]]]);
	}
	cout << ans;
	return 0;
}
2024/7/25 11:01
加载中...