题目链接

luogu P1401 城市

题解

二分最小边权,dinic检验

代码

// luogu-judger-enable-o2

/*

二分最小边权,dinic检验

*/

#include<queue>

#include<cctype>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

inline int read() {

    int x = 0,f = 1;

    char c = getchar();

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

    while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();

    return x * f;

}

#define INF 1e9 + 7

const int maxn = 40007;

struct node {

    int u,v,w,next;

    bool operator < (const node & a) const {

        return w < a.w;

    }

} e[maxn];

int head[maxn],num = 1;

struct Node {

    int v,flow,next;

} edge[maxn << 2];

inline void add_edge(int u,int v,int flow ) {

    edge[++ num].v = v;edge[num].next = head[u];head[u] = num; edge[num].flow = flow;

    edge[++ num].v = u;edge[num].next = head[v];head[v] = num; edge[num].flow = flow;

}

int cur[maxn];

int S = 1,T ;

int n,m,t;

std::queue<int>q;

int lev[maxn];

bool bfs() {

    for(int i = 0;i <= n;++ i) cur[i] = head[i];

    for(int i = 0;i <= n;++ i) lev[i] = -1;

    q.push(S),lev[S] = 0;

    while(!q.empty()) {

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

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

            if(edge[i].flow > 0 && lev[edge[i].v] == -1) lev[edge[i].v] = lev[u] + 1,q.push(edge[i].v);

    }

    return lev[T] != -1;

}

int dfs(int now,int flow) {

    if(now == T) return flow;

    int rest = 0 , delta;

    for(int &i = cur[now];i;i = edge[i].next) {

        int v = edge[i].v;

        if(lev[v] != lev[now] + 1 || edge[i].flow <= 0) continue;

        delta = dfs(v,std::min(flow - rest,edge[i].flow));

        if(delta) {

            edge[i].flow -= delta;

            edge[i ^ 1].flow += delta;

            rest += delta; if(rest == flow) break;

        }

    }

    if(rest == flow) lev[now] = -1;

    return rest;

}

int dinic() {

    int ret = 0;

    while(bfs()) ret += dfs(S,INF);

    return ret;

}

bool check(int x) {

    num = 1;

    memset(head,0,sizeof head);

    for(int i = 1;i <= m;++ i)

        if(e[i].w <= x) add_edge(e[i].u,e[i].v,1);

        else break;

    return dinic() >= t;

}

int main() {

    n = read(),m = read(),t = read(); T = n;

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

    std::sort(e + 1, e + m + 1);

    int l = 0,r = 100000007;

    int ans = -1;

    while(l <= r) {

        int mid = l + r >> 1;

        if(check(mid)) ans = mid , r = mid - 1;

        else l = mid + 1;

    }

    printf("%d\n",ans);

    return 0;

}