縮點+dp bzoj1179 apio搶掠計劃

好水的題啊好久沒做這麼水的題了。。。

不過似乎是好久沒做題了。。。

用tarjan随便縮下點，然後就成了有向無環圖了

這樣的話就很好說了

可以用spfa

不過其實随便搞個隊列然後dp

或者可以叫bfs一下就可以了。。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<vector>
#include<queue>
#define pb push_back
#define MAX 500000
#define read(x) scanf("%d",&x)
#define rep(x,y,z) for(int x=y;x<=z;x++)

using namespace std;

int n,m,k,value[MAX],money[MAX],dfn[MAX],pre[MAX],dfs_clock=0,scc_num=0;
int scc[MAX],in[MAX],ans=-0x7777ffff;
int bar[MAX],begin,Begin,f[MAX],can[MAX];

stack<int>s;
vector<int>aim[MAX];
vector<int>graph[MAX];

void tarjan(int x)
{
	dfn[x]=pre[x]=++dfs_clock;
	s.push(x);
	in[x]=1;
	for(int i=0;i<aim[x].size();i++)
	{
		int now=aim[x][i];
		if(!dfn[now])
		{
			tarjan(now);
			pre[x]=min(pre[x],pre[now]);
		}
		else
		{
			if(in[now])
				pre[x]=min(pre[x],dfn[now]);
		}
	}
	if(dfn[x]==pre[x])
	{
		scc_num++;
		while(!s.empty())
		{
			int now=s.top();
			s.pop();
			in[now]=0;
			scc[now]=scc_num;
			if(now==x)
				break;
		}
	}
	return;
}

void make_graph()
{
	rep(i,1,n)
		money[scc[i]]+=value[i];
	rep(i,1,n)
		for(int j=0;j<aim[i].size();j++)
		{
			int now=aim[i][j];
			if(scc[i]!=scc[now])
				graph[scc[i]].pb(scc[now]);
		}
	return;
}

void calc()
{
	memset(f,0,sizeof(f));
	queue<int>q;
	begin=scc[Begin];
	q.push(begin);
	f[begin]=money[begin];
	while(!q.empty())
	{
		int now=q.front();
		q.pop();
		for(int i=0;i<graph[now].size();i++)
		{
			int w=graph[now][i];
			if(f[w]<money[w]+f[now])
			{
				f[w]=money[w]+f[now];
				q.push(w);
			}
		}
	}
	return;
}

void work()
{
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i);

	rep(i,1,k)
		can[scc[bar[i]]]=1;

	make_graph();
	calc();
}

int main()
{
	memset(in,0,sizeof(in));
	memset(dfn,0,sizeof(dfn));
	memset(money,0,sizeof(money));
	memset(can,0,sizeof(can));
	read(n),read(m);
	int x,y;
	rep(i,1,m)
		read(x),read(y),aim[x].pb(y);
	rep(i,1,n)
		read(value[i]);
	read(Begin);
	read(k);
	rep(i,1,k)
		read(bar[i]);
	
	work();

	rep(i,1,scc_num)
		if(can[i])
			ans=max(ans,f[i]);
	printf("%d\n",ans);
	return 0;
}