写在前面

今天来水主题库里的有水分的紫题，随便一翻竟然找到宝了。

小清新二分 + 网络流。

算法思路

考虑到题目中限制的是最大边权，要求最大边权最小，那么很容易想到二分答案。

单调性的证明：最大边权是对可行的边的一个限制，因此这个值越大，对可行的边的限制放的就越宽，可供选择的边就不会变少。凑齐 \(t\) 条边的机会不会变小。满足单调性。

考虑到要找到 \(t\) 条可行路径，可以抽象成为在所有边权的容量都为 \(1\) 的情况下，最大流不小于 \(t\)。

求解最大流这里我使用的 dinic 算法。

dinic 算法的时间复杂度为 \(\mathcal O(n^2m)\)，实际上远远跑不满，而且它有各种虽然不影响渐进时间复杂度，但是能够大大提高实际运行效率的优化和剪枝。因此实际运行效率极高。

Tips

• 注意存双向边、数组越界和每次清空。

Code

#include <bits/stdc++.h>

namespace Basic {
    template <typename Temp> inline void read(Temp & res) {
        Temp fh = 1; res = 0; char ch = getchar();
        for(; !isdigit(ch); ch = getchar()) if(ch == '-') fh = -1;
        for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ '0');
        res = res * fh;
    }
}

using namespace Basic;
using namespace std;

const int Maxn = 2e2 + 5;
const int Maxm = 8e4 + 5;

int n, m, t, x, y, z;
int l = 0, r = 0x7fffffff, mid, ans;

struct e {
    int to, nxt, f;
} b[Maxm];
int head[Maxn], ecnt;
inline void add(int u, int v, int fl) {b[++ecnt] = (e) {v, head[u], fl}; head[u] = ecnt;}

struct edg {
    int v_1, v_2, length;
} b0[Maxm];

queue<int> q;
int dep[Maxn], cur[Maxn];
bool bfs() {
    memset(dep, 0, sizeof(dep));
    while(!q.empty()) q.pop();
    q.push(1); dep[1] = 1;
    while(!q.empty()) {
        int tnow = q.front(); q.pop();
        for(register int i = head[tnow]; i; i = b[i].nxt) {
            int tto = b[i].to, tf = b[i].f;
            if((dep[tto]) || (!tf)) continue;
            dep[tto] = dep[tnow] + 1;
            q.push(tto);
            if(tto == n) return true;
        }
    }
    return false;
}

int dfs(int t, int flow) {
    if(t == n) return flow;
    int rest = flow;
    for(; cur[t] && rest; cur[t] = b[cur[t]].nxt) {
        int tto = b[cur[t]].to, tf = b[cur[t]].f;
        if((dep[tto] != dep[t] + 1) || (!tf)) continue;
        int res = dfs(tto, min(tf, rest));
        rest -= res; b[cur[t]].f -= res; b[cur[t] ^ 1].f += res;
        if(!res) dep[tto] = 0;
        if(!rest) return flow;
    }
    return flow - rest;
}

bool check(int lim) {
    int Maxflow = 0;
    memset(head, 0, sizeof(head)); ecnt = 1;
    for(register int i = 1; i <= m; ++i) {
        if(b0[i].length <= lim) {
            add(b0[i].v_1, b0[i].v_2, 1);
            add(b0[i].v_2, b0[i].v_1, 1);
        }
    }
    while(bfs()) {
        memcpy(cur, head, sizeof(cur));
        Maxflow += dfs(1, 0x7fffffff >> 1);
    }
    return Maxflow >= t;
}

int main() {
    read(n); read(m); read(t);
    for(register int i = 1; i <= m; ++i) {read(b0[i].v_1); read(b0[i].v_2); read(b0[i].length);}
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    printf("%d", ans);
    return 0;
}