寒鸽儿のBlog

在有向图中,边又没啥限制,因而考虑缩点。缩点的同时记录该点内部有无酒吧以及该点的总钱数。

缩完点之后,很自然地得到一个DAG。只要抢,就连同该DAG中的点一起包圆。
然后我们可以在DAG上跑DP,根据tarjan的性质,缩点的编号是逆拓扑序的,因此只要按从起点所在点出发结点序递减的顺序递推即可,每次推到有酒吧的点更新答案。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 567890;

int head[N<<1], ver[N<<1], nex[N<<1], my[N<<1], tot, n;
inline void addedge(int u, int v) {
	ver[tot] = v; nex[tot] = head[u]; my[tot] = u; head[u] = tot++;
}

int a[N], isba[N], s;

int dfn[N], low[N], co[N], bar[N], mon[N], sta[N], dfs_clock = 1, col = 1, top;
void tarjan(int cur) {
	dfn[cur] = low[cur] = dfs_clock++;
	sta[top++] = cur;
	for(int i = head[cur]; ~i; i = nex[i])
		if(!dfn[ver[i]]) {
			tarjan(ver[i]);
			low[cur] = min(low[cur], low[ver[i]]);
		} else if(!co[ver[i]]) {
			low[cur] = min(low[cur], dfn[ver[i]]);
		}
	if(dfn[cur] == low[cur]) {
		--top;
		while(sta[top] != cur) {
			if(isba[sta[top]]) bar[col] = 1;
			mon[col] += a[sta[top]];
			co[sta[top--]] = col;
		}
		co[cur] = col;
		mon[col] += a[cur];
		if(isba[cur]) bar[col] = 1;
		++col;
	}
}

int f[N], ans;

int main() {
	memset(head, -1, sizeof(head));
	int m, u, v, p;
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; ++i) {
		scanf("%d %d", &u, &v);
		addedge(u, v);
	}
	for(int i = 1; i <= n; ++i) scanf("%d", a + i);
	scanf("%d %d", &s, &p);
	while(p--) scanf("%d", &u), isba[u] = 1;
	for(int i = 1; i <= n; ++i) if(!dfn[i]) tarjan(i);
	--col;
	for(int i = 0, end = tot; i < end; ++i) 
		if(co[my[i]] != co[ver[i]])
			addedge(co[my[i]] + n, co[ver[i]]);
	for(int i = co[s]; i; --i) {
		f[i] += mon[i];
		if(bar[i]) ans = max(ans, f[i]);
		for(int j = head[i+n]; ~j; j = nex[j])
			f[ver[j]] = max(f[ver[j]], f[i]);
	}
	printf("%d\n", ans);
	return 0;
}