这题只要想到了不是特别难,主要是很难想到判断有没有T条边不重合的路径居然是用最大流来做
/*
* 这题说的是给你一个网络,要求你从1号点出发走到N号点走T次
* 并且呢数据保证一定至少有T条边不重合的路径。
* 要求你找出来怎样的T条边不重合的路径可以使得这T条路径里面所有的边的最大值最小
* 那这种最大值的最小化问题肯定是用二分来做嘛。
* 假设我们手头的二分区间是[L, R],mid = (L + R) >> 1,
* 最后的答案是ans,也就是说存在T条边不重合的路径,这T条路径里面的每条边长度都是<= ans的
* 并且你任取T条边不重合的路径,这T条路径里面边的最大值一定>= ans
* 好的那么假设mid >= ans,我们应该就可以找到T条边不重合的路径使得这T条路径的每条边长度都是<= mid的吧
* 那么用最大流来建模应该就是当某条边的长度<= mid的时候我们让他出现,容量是1。然后求一下1到N的最大流看看有没有>= T吧
* 因为上面这个边出现的时候容量是1啊,所以只要流过去了肯定不会有重合的边的。
*/
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 300, M = 40010 << 2;
// 这里为什么要M << 2呢?就是为什么边数要开4倍呢?
int n, m, t, S, T;
int fi[N], ne[M], en[M], w[M], len[M], idx = 0;
void add(int a, int b, int c) {
idx++;
ne[idx] = fi[a];
fi[a] = idx;
en[idx] = b;
len[idx] = c;
}
int q[N], head, tail, cur[N], d[N];
bool bfs() {
head = 1, tail = 0;
q[++tail] = S, cur[S] = fi[S];
for (int i = 1; i <= n; i++) d[i] = -1;
d[S] = 0;
while (tail - head + 1 > 0) {
int u = q[head++];
for (int p = fi[u]; p > 0; p = ne[p]) {
int v = en[p];
if (d[v] != -1 || !w[p * 2 - 1]) continue;
q[++tail] = v, cur[v] = fi[v], d[v] = d[u] + 1;
}
}
if (d[T] == -1) return false;
return true;
}
int find(int u, int minw) {
if (u == T) return minw;
for (int p = cur[u]; p > 0; p = ne[p]) {
int v = en[p];
if (d[v] != d[u] + 1 || !w[p * 2 - 1]) continue;
int res = find(v, min(minw, w[p * 2 - 1]));
if (res == 0) { cur[u] = ne[p]; continue; }
w[p * 2 - 1] -= res;
w[p * 2] += res;
return res;
}
return 0;
}
int dinic() {
int r = 0, flow;
while (bfs()) {
while (true) {
flow = find(1, 1e8);
if (flow == 0) break;
r += flow;
}
}
return r;
}
bool check(int mid) {
// 这个函数就是看看mid <= ans是否成立
for (int i = 1; i <= m * 4; i++) w[i] = 0;
// 看到这里应该要明白为什么边数开4倍了,很简单呀,给你的图是双向边嘛,然后1条边在残留网络里面是对应过去过来2条边的,所以就是4倍了
for (int i = 1; i <= n; i++) {
for (int p = fi[i]; p > 0; p = ne[p]) {
if (len[p] <= mid) w[2 * p - 1] = 1;
}
}
if (dinic() >= t) return true;
return false;
}
int main() {
scanf_s("%d%d%d", &n, &m, &t);
for (int i = 1; i <= m; i++) {
int a, b, c;
scanf_s("%d%d%d", &a, &b, &c);
add(a, b, c); add(b, a, c);
}
S = 1, T = n;
int L = 1, R = 1e6;
while (L < R) {
int mid = (L + R) >> 1;
if (check(mid)) R = mid;
else L = mid + 1;
}
printf_s("%d\n", L);
}
// 好了上面的代码已经AC了,2021年8月20日21:11:48