BZOJ 1733: [Usaco2005 feb]Secret Milking Machine 神秘的挤奶机 网络流 + 二分答案

#include <cstdio> 
#include <algorithm>  
#include <vector> 
#include <cstring>  
#include <queue>    
#define ll long long 
#define setIO(s) freopen(s".in","r",stdin) 
#define maxn 100000   
#define inf 230  
using namespace std;   
int n,m,cc,S,T;        
struct Dinic { 
    struct Edge {
        int from,to,cap; 
        Edge(int from=0,int to=0,int cap=0):from(from),to(to),cap(cap){}  
    };   
    queue<int>Q;    
    vector<Edge>edges;   
    vector<int>G[300];     
    int current[300],d[300],vis[300];        
    void addedge(int u,int v,int c) {
        edges.push_back(Edge(u,v,c)); 
        edges.push_back(Edge(v,u,0)); 
        int o=edges.size();  
        G[u].push_back(o-2);  
        G[v].push_back(o-1);          
    }    
    int BFS() {   
        memset(vis,0,sizeof(vis)), memset(d,0,sizeof(d));      
        vis[S]=1,d[S]=0;
        Q.push(S); 
        while(!Q.empty()) {
            int u=Q.front(); Q.pop();   
            for(int i=0;i<G[u].size();++i) {
                Edge e=edges[G[u][i]];  
                if(e.cap>0 && !vis[e.to]) {
                    vis[e.to]=1, d[e.to]=d[u]+1;        
                    Q.push(e.to);    
                }
            }  
        }
        return vis[T];    
    } 
    int dfs(int x,int cur) { 
        if(x==T) return cur;   
        int f,flow=0; 
        for(int i=current[x];i<G[x].size();++i) {
            current[x]=i; 
            Edge e=edges[G[x][i]];   
            if(d[e.to]==d[x]+1 && e.cap > 0) {
                f=dfs(e.to,min(cur, e.cap));  
                if(f) {
                    cur-=f, flow+=f, edges[G[x][i]].cap-=f, edges[G[x][i]^1].cap+=f;          
                    if(cur<=0) return flow;         
                }
            }               
        }  
        return flow;   
    }                  
    int maxflow() {        
        int re=0; 
        while(BFS()) memset(current,0,sizeof(current)),re+=dfs(S,inf);  
        return re;    
    } 
    void re() {
        edges.clear();     
        for(int i=0;i<300;++i) G[i].clear();   
    }
}net;              
struct Node {
    int u,v,c;     
}nd[maxn];     
bool cmp(Node a,Node b) {
    return a.c < b.c; 
}
int check(int t) { 
    net.re();   
    for(int i=1;i<=t;++i) {
        net.addedge(nd[i].u,nd[i].v,1); 
        net.addedge(nd[i].v,nd[i].u,1);   
    } 
    return net.maxflow() >= cc;   
}
int main() { 
    // setIO("input"); 
    scanf("%d%d%d",&n,&m,&cc);    
    for(int i=1;i<=m;++i) scanf("%d%d%d",&nd[i].u,&nd[i].v,&nd[i].c);       
    sort(nd+1,nd+1+m,cmp);        
    int l=1,r=m,mid,ans=0; 
    S=1,T=n;   
    while(l<=r) {
        mid=(l+r)>>1;    
        if(check(mid)) ans=mid, r=mid-1;   
        else l=mid+1;   
    } 
    printf("%d\n",nd[ans].c);         
    return 0;    
}