检查站
题目链接。cnblogs。
Problem
小 I 是一个巨大的铁路公司的主管，他管理着 n 个火车站，用 1 至 n 的整数给它们编号。铁路公司有 c 个分部，第 i 个分部的办公室位于火车站 p_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;
}
```