AtCoder Beginner Contest 214 H Collecting

// Problem: H - Collecting
// Contest: AtCoder - AtCoder Beginner Contest 214
// URL: https://atcoder.jp/contests/abc214/tasks/abc214_h
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 1000100;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;

ll n, m, K, a[maxn], b[maxn], c[maxn], head[maxn], len = 1, ntot, id[maxn][2], S, T;
ll dfn[maxn], low[maxn], scc[maxn], times, tot, stk[maxn], top;
vector<int> G[maxn];

struct edge {
	ll from, to, next, cap, flow, cost;
} edges[maxn * 5];

inline void add_edge(ll u, ll v, ll c, ll f, ll co) {
	edges[++len].from = u;
	edges[len].to = v;
	edges[len].next = head[u];
	edges[len].cap = c;
	edges[len].flow = f;
	edges[len].cost = co;
	head[u] = len;
}

void dfs(int u) {
	dfn[u] = low[u] = ++times;
	stk[++top] = u;
	for (int v : G[u]) {
		if (!dfn[v]) {
			dfs(v);
			low[u] = min(low[u], low[v]);
		} else if (!scc[v]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (low[u] == dfn[u]) {
		++tot;
		while (1) {
			int x = stk[top--];
			scc[x] = tot;
			b[tot] += a[x];
			if (x == u) {
				break;
			}
		}
	}
}

struct node {
	ll u, d;
	node(ll a = 0, ll b = 0) : u(a), d(b) {}
};

inline bool operator < (const node &a, const node &b) {
	return a.d > b.d;
}

struct MCMF {
	ll d[maxn], h[maxn], p[maxn], f[maxn];
	bool vis[maxn];
	
	inline void add(ll u, ll v, ll c, ll co) {
		add_edge(u, v, c, 0, co);
		add_edge(v, u, 0, 0, -co);
	}
	
	inline bool dij() {
		for (int i = 1; i <= ntot; ++i) {
			vis[i] = 0;
			d[i] = inf;
		}
		priority_queue<node> pq;
		pq.emplace(S, 0);
		d[S] = 0;
		f[S] = inf;
		while (pq.size()) {
			int u = pq.top().u;
			pq.pop();
			if (vis[u]) {
				continue;
			}
			vis[u] = 1;
			for (int i = head[u]; i; i = edges[i].next) {
				edge &e = edges[i];
				if (d[e.to] > d[u] + e.cost + h[u] - h[e.to] && e.cap > e.flow) {
					d[e.to] = d[u] + e.cost + h[u] - h[e.to];
					p[e.to] = i;
					f[e.to] = min(f[u], e.cap - e.flow);
					if (!vis[e.to]) {
						pq.emplace(e.to, d[e.to]);
					}
				}
			}
		}
		return d[T] < inf;
	}
	
	pii solve() {
		ll flow = 0, cost = 0;
		while (dij()) {
			for (int i = 1; i <= ntot; ++i) {
				h[i] = min(h[i] + d[i], inf);
			}
			flow += f[T];
			cost += f[T] * h[T];
			for (int u = T; u != S; u = edges[p[u]].from) {
				edges[p[u]].flow += f[T];
				edges[p[u] ^ 1].flow -= f[T];
			}
		}
		return make_pair(flow, cost);
	}
} solver;

void solve() {
	scanf("%lld%lld%lld", &n, &m, &K);
	while (m--) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].pb(v);
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
	}
	for (int i = 1; i <= n; ++i) {
		if (!dfn[i]) {
			dfs(i);
		}
	}
	reverse(b + 1, b + tot + 1);
	for (int i = 1; i <= n; ++i) {
		scc[i] = tot - scc[i] + 1;
	}
	for (int i = 1; i <= tot; ++i) {
		c[i] = c[i - 1] + b[i];
	}
	S = ++ntot;
	T = ++ntot;
	for (int i = 1; i <= tot; ++i) {
		id[i][0] = ++ntot;
		id[i][1] = ++ntot;
	}
	set<pii> st;
	for (int u = 1; u <= n; ++u) {
		for (int v : G[u]) {
			int x = scc[u], y = scc[v];
			if (x != y && st.find(make_pair(x, y)) == st.end()) {
				st.emplace(x, y);
				solver.add(id[x][1], id[y][0], inf, c[y - 1] - c[x]);
			}
		}
	}
	for (int i = 1; i <= tot; ++i) {
		solver.add(id[i][0], id[i][1], 1, 0);
		solver.add(id[i][0], id[i][1], inf, b[i]);
		solver.add(id[i][1], T, inf, c[tot] - c[i]);
	}
	solver.add(S, id[scc[1]][0], K, c[scc[1] - 1]);
	pii ans = solver.solve();
	printf("%lld\n", c[tot] * K - ans.scd);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}