检查站

题目链接。

Problem

小 I 是一个巨大的铁路公司的主管，他管理着 \(n\) 个火车站，用 \(1\) 至 \(n\) 的整数给它们编号。铁路公司有 \(c\) 个分部，第 \(i\) 个分部的办公室位于火车站 \(p_i\)。可能有火车站没有分部办公室，一个火车站也有可能有多个分部办公室。

\(n\) 个火车站之间由 \(m\) 条单向铁路连接，其中第 \(i\) 条铁路由火车站 \(u_i\) 连向 \(v_i\)，属于分部 \(r_i\) 管辖。为了保证管理方便，分部 \(r_i\) 的办公室要么在 \(u_i\)，要么在 \(v_i\)。

火车站 \(1\)（港口）和 \(n\)（首都）是公司管辖范围内最繁忙的车站。为了保障进口货物安全，根据交通运输部的要求，小 I 需要在一些铁路上设立检查站，使得从火车站 \(1\) 到火车站 \(n\) 的所有可能路线上都有一个有检查站的铁路。

小 I 可以通知一些分部（也可以不通知任何分部），要求这些分部在它们管理的所有铁路上设立检查站。小 I 想知道，最少需要通知多少个分部才可以达到要求。作为新上任的算法工程师，你准备给小 I 露一手。

数据范围：\(2 \le n, m, c \le 5\times 10^4\)。

Sol

这个东西感觉很能想到网络流啊，数据范围这么尴尬。

原问题显然不弱于最小割。当每个分部至多管辖一条边的时候，就是权为 \(1\) 的最小割。

考虑最小割。割掉一个分部可以干掉所有通过它连出去和连进来的边。但是这里是割一个点，把点拆成入点和出点即可。然后出点连向所有通过该分部出去的边的 \(v\)，所有通过该分部连进去的边的 \(u\) 连向入点即可。

具体的连边方式：

点 \(i \in [1, n] \cap \mathbb{Z}\) 表示原图中的点，\([n + 1, n + c] \cap \mathbb{Z}\) 与 \([n + c + 1, n + c + c] \cap \mathbb{Z}\) 分别表示分部的入点与出点。

对于分部 \(i\)，连边 \((p_i, n + i, +\infty), (n + c + i, p_i, +\infty), (n + i, n + c + i, 1)\)。

对于边 \((u, v, r)\)（\(u \ne v\)）：

• 若 \(p_r = u\)：连边 \((n + c + r, v, +\infty)\)。
• 否则连边 \((u, n + r, +\infty)\)。

求以 \(1\) 为源，\(n\) 为汇的最小割。

时间复杂度不是很会分析/ng。能过就行。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
mt19937_64 eng(time(0) ^ clock());
template<typename T>
T rnd(T l, T r) { return eng() % (r - l + 1) + l; }
struct Flow {
	const ll inf = 1e18;
	int n, S, T;
	struct node {
		int v; ll w; int b;
		node(int _v, ll _w, int _b) {
			v = _v, w = _w, b = _b;
		}
	};
	vector<vector<node>> e;
	vector<int> dis, cur, q;
	Flow(int _n) : e(_n + 10), dis(_n + 10), cur(_n + 10), q(_n + 10) {
		n = _n;
	}
	void adde(int u, int v, ll w) {
		// cout << u << " " << v << " " << w << "\n";
		e[u].emplace_back(v, w, (int)e[v].size());
		e[v].emplace_back(u, 0, (int)e[u].size() - 1);
	}
	int hd, tl;
	bool bfs() {
		for(int i = 0; i <= n; ++i) dis[i] = cur[i] = 0;
		q[hd = tl = 1] = S;
		dis[S] = 1;
		while(hd <= tl) {
			int u = q[hd++];
			for(auto i : e[u]) {
				int v = i.v;
				if(i.w && !dis[v]) {
					dis[v] = dis[u] + 1;
					q[++tl] = v;
					if(i.v == T) return 1;
				}
			}
		}
		return 0;
	}
	ll dfs(int u, ll flow) {
		if(u == T) return flow;
		ll res = 0;
		for(int &i = cur[u]; i < (int)e[u].size(); ++i) {
			int v = e[u][i].v;
			if(e[u][i].w && dis[v] == dis[u] + 1) {
				ll fl = dfs(v, min(flow, e[u][i].w));
				e[u][i].w -= fl, e[v][e[u][i].b].w += fl;
				flow -= fl, res += fl;
				if(!flow) return res;
			}
		}
		return res;
	}
	ll maxflow(int _S, int _T) {
		S = _S, T = _T;
		ll res = 0;
		while(bfs()) res += dfs(S, inf);
		return res;
	}
};
int n, m, c;
int p[100005];
int main() {
	scanf("%d%d%d", &n, &m, &c);
	Flow G(n + c + c);
	for (int i = 1; i <= c; i++)
		scanf("%d", p + i), G.adde(p[i], n + i, 1e9), G.adde(n + i + c, p[i], 1e9), G.adde(n + i, n + i + c, 1);
	for (int i = 1, u, v, r; i <= m; i++) {
		scanf("%d%d%d", &u, &v, &r);
		if (u == v)
			continue;
		if (p[r] == u)
			G.adde(n + r + c, v, 1e9);
		else if (p[r] == v)
			G.adde(u, n + r, 1e9);
	}
	cout << G.maxflow(1, n) << "\n";
	return 0;
}