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
",ans); 
    return 0; 
}