[APIO2009] 스윕 계획(강연통 컴포넌트+축소점+토폴로지 정렬+dp)

제목:
지정된 시작점에서 시작하여 임의의 지정된 끝점까지 멈추는 지향도를 지정하여 지나간 모든 결점의 최대 점권과포인트, 모서리 수<=500000
하나의 강연통분량 내의 점은 서로 도달할 수 있기 때문에 그 중의 한 점을 통과하려면 그것이 있는 강연통분량 내의 모든 점을 통과해야 하기 때문에 하나의 강연통분량을 하나의 점으로 축소해야 한다
이렇게 하면 유방향 무환도를 얻을 수 있는데, 그림에서 dp를 얻으면 된다
먼저 모든 시작점에서 도달할 수 있는 점에 대해 토폴로지 정렬을 한 번 한 다음에 대기열로 입도 0의 점을 유지하고 매번 대기열의 첫 번째 요소를 꺼내서 그 답안으로 다른 점을 업데이트하면 된다
리할 줄 아는 점이 하나 있는 것 같은데?

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int u[500005],v[500005],w[500005],first[500005],next[500005],bar[500005],f[500005],d[500005],vis[500005];
int pre[500005],link[500005],sta[500005],sccno[500005],q[500005];
int clo=0,top=0;
void find(int x)
{
	int i,y;
	pre[x]=link[x]=++clo;
	sta[++top]=x;
	for(i=first[x];i!=0;i=next[i])
		if(sccno[v[i]]==0)
		{
			if(pre[v[i]]==0) find(v[i]);
			if(link[x]>link[v[i]]) link[x]=link[v[i]];
		}
	if(pre[x]==link[x])
	{
		while(sta[top]!=x) sccno[sta[top--]]=x;
		sccno[sta[top--]]=x;
	}
}
void dfs(int x)
{
	int i;
	vis[x]=1;
	for(i=first[x];i!=0;i=next[i])
		if(vis[v[i]]==0) dfs(v[i]);
}
int main()
{
	int n,m,s,p,i,head=0,tail=0,max=0;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&u[i],&v[i]);
		next[i]=first[u[i]];
		first[u[i]]=i;
	}
	for(i=1;i<=n;i++)
		scanf("%d",&w[i]);
	scanf("%d%d",&s,&p);
	for(i=1;i<=p;i++)
		scanf("%d",&bar[i]);
	for(i=1;i<=n;i++)
		if(sccno[i]==0) find(i);//        
	memset(first,0,sizeof(first));
	memset(next,0,sizeof(next));
	for(i=1;i<=m;i++)//   
	{
		u[i]=sccno[u[i]];
		v[i]=sccno[v[i]];
		if(u[i]!=v[i])
		{
			next[i]=first[u[i]];
			first[u[i]]=i;
		}
	}
	for(i=1;i<=n;i++)
		if(sccno[i]!=i) w[sccno[i]]+=w[i];
	dfs(sccno[s]);
	for(i=1;i<=m;i++)
		if(u[i]!=v[i]&&vis[u[i]]==1) f[v[i]]++;
	q[tail++]=sccno[s];
	while(head<tail)
	{
		d[q[head]]+=w[q[head]];
		for(i=first[q[head]];i!=0;i=next[i])
		{
			if(d[v[i]]<d[u[i]]) d[v[i]]=d[u[i]];
			f[v[i]]--;
			if(f[v[i]]==0) q[tail++]=v[i];
		}
		head++;
	}
	for(i=1;i<=p;i++)
		if(max<d[sccno[bar[i]]]) max=d[sccno[bar[i]]];
	printf("%d",max);
	return 0;
}