秘密挤奶机问题

解题思路

给定一个无向图，让我们从 $1$ 走到 $n$ 走 $T$ 次，且每条边只能走一次，求出经过的所有边中最大的边最小。

凡是问最大值最小的问题一般都可以考虑二分，所以需要看一下本题是否具有单调性或二段性。

每条边的长度范围在 $[1, 10^6]$ 以内，这就是二分的范围，假设走 $T$ 次后最大边的最小值是 $res$，说明用长度在 $[1, mid]$ 以内的所有边是能从 $1$ 走到 $n$ 走 $T$ 次的。可以发现，如果取 $< res$ 的值为答案，那么一定无解，反之，取 $>= res$ 的值为答案，那么一定有解，因此整个范围是具有二段性的。

综上所述，我们可以使用二分来找出最大边的最小值，具体思路就是每次从范围区间中取一个中间值 $mid$，如果用长度在 $[1, mid]$ 范围内的所有边无法走 $T$ 次，说明 $mid$ 处于左半区间，则 $res > mid$，需要二分右区间，反之，如果用长度在 $[1, mid]$ 范围内的所有边能够走 $T$ 次，说明 $mid$ 处于右半区间，则 $res <= mid$，需要二分左区间。直到范围缩小到一个固定的值，这个值就是 $res$。

目前还剩下一个问题，我们还需要判断一下，对于一个中间值 $mid$，用长度在 $[1, mid]$ 范围内的所有边能否走 $T$ 次。能完成这个判断，我们才可以进一步二分。

这个判定问题，我们就可以用到最大流，我们目前需要知道在原图 $G$ 中是否存在 $T$ 条没有公共边的路径，我们需要构建一个流网络 $G’$，使得任意一组可行解（任意一组没有公共边的 $T$ 条路径）都能和 $G’$ 的一个可行流 $f’$ 一一对应。

注意，这里解决一个隐含的问题，本题需要将无向图转化成流网络，但是我们之前对于网络流的一系列推导都是基于没有反向边的情况下证明的，那么在无向图中是否能成立呢，这里我们可以人为的进行一些处理，对于两个点之间存在反向边，如下图

我们可以如下图这样加入一个额外的点，使它变成一个环，那么就不存在反向边了，基于这个思想就能保证之前的推导都是成立的，当然在代码实现中并不需要实现具体的加点操作，直接建立反向边就行。

然后我们需要构建流网络 $G’$，我们可以将起点 $1$ 号点作为源点，将终点 $n$ 号点作为汇点，由于每条边都只能走一次，因此设置每条边的容量都为 $1$，然后求一下从源点到汇点的最大流，这个最大流的流量就表示从 $1$ 到 $n$ 存在多少条不存在公共边的路径，如果流量$>= T$，说明有解，否则说明无解。对应的进行二分处理即可。

这里很明显原图的可行解和流网络的可行流是一一对应的，这里就不过多证明，可以参照之前的问题进行类似的证明即可。

这里有些细节需要注意，一个是由于每条边都存在正向边和反向边，我们在建图的时候设置了正向边和反向边都存在 $1$ 的容量，意味着每条边都可以来回走一次，但是题目要求每条边只能走一次，这里是否没法对应了呢，还是可以对应的，因为对于流网络来说，走过去走回来，在流量上来看等价于不走这条边，并且把这条边删去仍能满足容量限制和流量守恒，因此仍是一个合法的可行流，不会影响结果的正确性。

另一个需要注意的是，每条边都是无向边，也就是一条正向边一条反向边，然后在残量网络中每条边都会多建立一条它的反向边，也就是说一条边在残量网络中建了四条边，如下图

两个实线是容量为 $1$ 的真实边，两个虚线是残量网络中的反向边，最开始的容量为 $0$，当然建立四条边也是可以的，但是这样过于浪费，我们可以将同向的一虚一实进行合并，合并就是容量上限相加，由于虚线的容量为 $0$，因此合并后其实就等价于一正一反两条实线，把虚线去掉即可。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 210, M = 80010, INF = 0x3f3f3f3f;

int n, m, k, S, T;
// w[] 表示边的容量
// l[] 表示边的长度
int h[N], e[M], w[M], l[M], ne[M], idx; //邻接表
int q[N], d[N], cur[N]; //队列、层数、当前弧

void add(int a, int b, int c) //添加边
{
    e[idx] = b, l[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, l[idx] = c, ne[idx] = h[b], h[b] = idx++;
}

bool bfs() //建立分层图，判断是否存在增广路径
{
    int hh = 0, tt = 0;
    q[0] = S;

    memset(d, 0, sizeof d);
    d[S] = 1;

    cur[S] = h[S];

    while(hh <= tt)
    {
        int t = q[hh++];

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];

            if(!d[j] && w[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];

                if(j == T) return true;

                q[++tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int flow) //求出从 u 能往汇点传输的最大流量，上限为 flow
{
    if(u == T) return flow;

    int rest = flow;
    for(int i = cur[u]; i != -1 && rest; i = ne[i])
    {
        cur[u] = i;

        int j = e[i];
        if(d[j] == d[u] + 1 && w[i])
        {
            int k = find(j, min(rest, w[i]));
            if(!k) d[j] = 0;

            w[i] -= k;
            w[i ^ 1] += k;
            rest -= k;
        }
    }
    return flow - rest;
}

int dinic() //dinic算法求最大流
{
    int maxf = 0, flow;
    while(bfs())
        while(flow = find(S, INF)) maxf += flow;
    return maxf;
}

bool check(int mid) //判断用长度在 [1, mid] 范围内的所有边能否从 1 到 n 走 k 次
{
    for(int i = 0; i < idx; i++) //初始化所有边的容量
        if(l[i] > mid) w[i] = 0; //需要删去的边容量为 0
        else w[i] = 1; //不需要删去的边容量为 1

    return dinic() >= k;
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);

    memset(h, -1, sizeof h); //初始化邻接表

    S = 1, T = n; //源点/汇点
    while(m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c); //添加边
    }

    //二分
    int l = 1, r = 1e6;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid)) r = mid; //当前有解，二分左区间
        else l = mid + 1; //当前无解，二分右区间
    }
    printf("%d\n", r);

    return 0;
}