https://qoj.ac/contest/506/problem/1359
problem
给定一张大小为 的有向图 。现在告诉你敌军大本营在节点 \(s\) 和友军基地在节点 \(t\)。你需要在每个点上放置一定数量的APERS bounding mine来杀伤敌方步兵。
为了达成战术效果，你需要保证任何一条从 \(s\) 到 \(t\) 的路径都会经过至少 \(K\) 个地雷。由于地理限制，每个节点上只能放置最多一个地雷，且在 \(u\) 号节点上安放一个地雷需要付出 \(c_u\) 的代价（可以在 \(s,t\) 上安）。
你需要计算出达成战术效果所需付出的最小代价。\(n\leq 200, m\leq 500, K\leq 5\)。
solution
因为 \(k=1\) 是最小割问题，考虑扩展最小割。
原本是拆成入点和出点，不妨多加几层，\((u, k, L)\to (u, k, R)\) 连 \(c_u\)，\((u, k, L)\to (u, k + 1, R)\) 连 \(\infty\)。这里的意思是，我的流经过这里，如果将下面的 \(c_u\) 割断，流就向上走一层，忽略这个地雷。但是流只有 \(K\) 次忽略地雷的机会。当我们找到让所有流都到不了汇点的方案，就是答案了。
然后就你感性理解一下为什么这样每个地雷只会割一次，就是说每个地雷只在最快到达它时踩过的地雷数那一层被割断，其他情况它上不去。
构造方案和网络流最小割一样。
复杂度是网络流复杂度，乱写能过。
code
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
template <int N, int M, class T>
struct graph {
int head[N + 10], nxt[M << 1], cnt;
struct edge {
int u, v;
T w;
} e[M << 1];
edge& operator[](int i) { return e[i]; }
void add(int u, int v, T w) { e[++cnt] = { u, v, w }, nxt[cnt] = head[u], head[u] = cnt; }
void link(int u, int v, T w) { add(u, v, w), add(v, u, w); }
graph() { memset(head, cnt = 0, sizeof head); }
};
template <int N, int M, class Cap>
struct mf_graph {
graph<N, M, Cap> g;
mf_graph() { ++g.cnt; }
void add(int u, int v, int cap) {
g.add(u, v, cap);
g.add(v, u, 0);
}
int pre[N + 10], mxf[N + 10];
bool bfs(int s, int t) {
queue<int> q;
q.push(s);
memset(pre, -1, sizeof pre);
pre[s] = 0;
mxf[s] = 1e9;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = g.head[u]; i; i = g.nxt[i]) {
int v = g[i].v;
if (g[i].w && pre[v] == -1)
pre[v] = i, q.push(v), mxf[v] = min(mxf[u], g[i].w);
}
}
return pre[t] != -1;
}
int flow(int s, int t, int lim) {
int flw = 0;
while (lim && bfs(s, t)) {
int f = min(mxf[t], lim);
lim -= f, flw += f;
for (int i = pre[t]; i; i = pre[g[i].u]) {
g[i].w -= f, g[i xor 1].w += f;
}
}
return flw;
}
int tot = 0;
};
int n, m, k, gs, gt, c[210], id[210][10][2];
graph<210, 510, int> g;
mf_graph<2100, 100010, int> mf;
int main() {
freopen("apers.in", "r", stdin);
freopen("apers.out", "w", stdout);
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> m >> k >> gs >> gt;
for (int i = 1; i <= n; i++) {
cin >> c[i];
for (int j = 1; j <= k; j++) mf.add(id[i][j][0] = ++mf.tot, id[i][j][1] = ++mf.tot, c[i]);
for (int j = 1; j < k; j++) mf.add(id[i][j][0], id[i][j + 1][1], 2e9 + 10);
if (i == gt)
for (int j = 1; j < k; j++) mf.add(id[i][j][1], id[i][j + 1][1], 2e9 + 10);//修正对无解的判断。
}
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
for (int j = 1; j <= k; j++) mf.add(id[u][j][1], id[v][j][0], 2e9 + 10);
}
int ret = mf.flow(id[gs][1][0], id[gt][k][1], 2e9 + 10);
cout << (ret == 2e9 + 10 ? -1 : ret) << endl;
return 0;
}