81pts在线求调
查看原帖
81pts在线求调
755850
Sword_wielder楼主2024/5/22 12:19
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e5 + 10;
int n, m, col, ans;
int c[N], cnt[N], u[N], v[N];
bool vis[N], o[N];
int val[N], ed[N], a[N];
vector <int> G, G1[N], G2[N], G3[N];

void dfs1(int u) {
	vis[u] = 1;
	for (auto v : G1[u])
		if (!vis[v]) 
			dfs1(v);
	G.push_back(u);
}

void dfs2(int u, const int t) {
	vis[u] = 1;
	for (auto v : G2[u])
		if (!vis[v])
			dfs2(v, t);
	c[u] = t, cnt[t] ++;
	val[t] += a[u];
}

int fa[N];
int Find(int u) {
	if (fa[u] == u) return u;
	return fa[u] = Find(fa[u]);
}

queue <int> q;
int dis[N];
signed main() {
	cin >> n >> m;
	for (int i = 1 ; i <= m ; i ++) {
		cin >> u[i] >> v[i];
		G1[u[i]].push_back(v[i]);
		G2[v[i]].push_back(u[i]);
	}
	for (int i = 1 ; i <= n ; i ++)
		cin >> a[i];
	int s, p; cin >> s >> p;
	for (int i = 1 ; i <= p ; i ++)
		cin >> ed[i];
	for (int i = 1 ; i <= n ; i ++)
		if(!vis[i]) dfs1(i);
	memset(vis, 0, sizeof(vis));
	for (int i = n - 1 ; i >= 0 ; i --)
		if (!vis[G[i]])
			dfs2(G[i], ++ col);
	for (int i = 1 ; i <= col ; i ++)
		fa[i] = i;
	for (int i = 1 ; i <= m ; i ++)
		if (Find(c[u[i]]) != Find(c[v[i]])) {
			int xx = Find(c[u[i]]), yy = Find(c[v[i]]);
			fa[xx] = yy;
			G3[c[u[i]]].push_back(c[v[i]]);
		}
	q.push(c[s]);
	for (int i = 1 ; i <= n ; i ++)
		dis[i] = -1e9;
	memset(vis, 0, sizeof(vis));
	dis[c[s]] = val[c[s]];
	while (!q.empty()) {
		int u = q.front(); q.pop();
		vis[u] = 0;
		for (auto v : G3[u]) 
			if (dis[v] < dis[u] + val[v]) {
				dis[v] = dis[u] + val[v];
				if (!vis[v]) {
					q.push(v);
					vis[v] = 1;
				}
			}
	}
	int ans = 0;
	for (int i = 1 ; i <= p ; i ++) 
		ans = max(ans, dis[c[ed[i]]]);
	cout << ans;
	return 0;
}
2024/5/22 12:19
加载中...