luoguP1401 城市

https://www.luogu.org/problemnew/show/P1401

二分答案网络流判断是否可行即可

#include <bits/stdc++.h>

using namespace std;

template <typename T>

inline void read(T &f) {

    f = 0; T fu = 1; char c = getchar();

    while (c < '0' || c > '9') {if (c == '-') fu = -1; c = getchar();}

    while (c >= '0' && c <= '9') {f = (f << 3) + (f << 1) + (c & 15); c = getchar();}

    f *= fu;

}

const int N = 200 + 5, M = 4e4 + 5, INF = INT_MAX;

struct Edge {

    int u, v, next, cap, flow;

}G[M << 1];

struct ele {

    int u, v, val;

    bool operator < (const ele A) const {return val < A.val;}

}p[M];

int head[N], nowhead[N], d[N];

int tot, n, m, t, S, T;

inline void addedge(int u, int v, int cap) {

    G[++tot] = (Edge) {u, v, head[u], cap, 0}, head[u] = tot;

    G[++tot] = (Edge) {v, u, head[v], cap, 0}, head[v] = tot;

}

int bfs() {

    memset(d, 0, sizeof(d));

    queue <int> q;

    d[S] = 1; q.push(S);

    while(!q.empty()) {

        int u = q.front(); q.pop();

        for(int i = head[u]; i; i = G[i].next) {

            int v = G[i].v;

            if(d[v] == 0 && G[i].cap > G[i].flow) {

                d[v] = d[u] + 1;

                q.push(v);

            }

        }

    }

    return d[T];

}

int dfs(int u, int Flow) {

    if(u == T || Flow == 0) return Flow;

    int flow = 0, f;

    for(int &i = nowhead[u]; i; i = G[i].next) {

        int v = G[i].v;

        if(d[v] == d[u] + 1 && (f = dfs(v, min(Flow, G[i].cap - G[i].flow))) > 0) {

            flow += f, Flow -= f;

            G[i].flow += f, G[i ^ 1].flow -= f;

            if(!Flow) break;

        }

    }

    return flow;

}

int dinic() {

    int ans = 0;

    while(bfs()) {

        for(int i = 1; i <= n; i++) nowhead[i] = head[i];

        ans += dfs(S, INF);

    }

    return ans;

}

int main() {

    read(n); read(m); read(t);

    for(int i = 1; i <= m; i++) read(p[i].u), read(p[i].v), read(p[i].val);

    sort(p + 1, p + m + 1);

    int l = 1, r = m; S = 1; T = n;

    while(l < r) {

        int mid = (l + r) >> 1;

        memset(head, 0, sizeof(head)); tot = 1;

        for(int i = 1; i <= mid; i++) addedge(p[i].u, p[i].v, 1);

        if(dinic() < t) l = mid + 1;

        else r = mid;

    }

    printf("%d\n", p[l].val);

    return 0;

}