BZOJ 1733: [Usaco2005 feb]Secret Milking Machine 神秘的挤奶机

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Description

约翰正在制造一台新型的挤奶机，但他不希望别人知道．他希望尽可能久地隐藏这个秘密．他把挤奶机藏在他的农场里，使它不被发现．在挤奶机制造的过程中，他需要去挤奶机所在的地方T(1≤T≤200)次．他的农场里有秘密的地道，但约翰只在返回的时候用它．农场被划分成N(2≤N≤200)块区域，用1到200标号．这些区域被P(1≤P≤40000)条道路连接，每条路有一个小于10^6的长度L．两块区域之间可能有多条道路连接．为了减少被发现的可能，约翰不会两次经过农场上的任何一条道路．当然了，他希望走最短的路．请帮助约翰寻找这T次从仓库走到挤奶机所在地的路线．仓库是区域1，挤奶机所在地是区域N．我们现在要求的是约翰经过的这些道路中最长的路的长度最小是多少，当然他不能重复走某一条路．请注意，我们要求的不是最短的总路程长度，而是所经过的直揍连接两个区域的道路中最长的道路的最小长度．数据保证约翰可以找到T条没有重复的从仓库到挤奶机所在区域的路．

Input

第1行是3个整数N、P和T，用空格隔开．

第2到P+1行，每行包括3个整数，Ai，Bi，Li．表示区域Ai、Bi之间有一条长度为Li的道路．

Output

输出只有一行，包含一个整数，即约翰经过的这些道路中最长的路的最小长度．

题解：

二分一个ans，网络流判断能不能到>=T次。

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#include <vector>

//  by zrt

//  problem:

//  无论你在什么时候开始，重要的是开始以后就不要停止。

using namespace std ;

typedef long long LL ;

const double eps(1e-10) ;

const int inf(0x3f3f3f3f) ;

int n,m,t;

int S,T;

struct N{

    int x,w;

    N(int a=0,int b=0){

        x=a,w=b;

    }

};

vector<N> v[205];

int H[205],X[80005],P[80005],tot,flow[80005];

inline void add(int x,int y,int z){

    P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;

}

int d[205];

queue<int> q;

bool bfs(){

    memset(d,0,sizeof d);

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

    while(!q.empty()){

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

        for(int i=H[x];i;i=X[i]){

            if(flow[i]>0&&!d[P[i]]){

                d[P[i]]=d[x]+1;

                q.push(P[i]);

            }

        }

    }

    return d[T];

}

int dfs(int x,int a){

    int f=a,tmp;

    if(x==T||a==0) return a;

    for(int i=H[x];i;i=X[i]){

        if(flow[i]>0&&d[P[i]]==d[x]+1){

            tmp=dfs(P[i],min(a,flow[i]));

            a-=tmp;

            flow[i]-=tmp;

            flow[i^1]+=tmp;

            if(!a) break;

        }

    }

    if(f==a) d[x]=-1;

//  printf("%d\n",f-a);

    return f-a;

}

int Dinic(){

    int f=0;

    while(f<=t&&bfs()) f+=dfs(S,t);

    return f;

}

bool judge(int lim){

    tot=1;

    memset(H,0,sizeof H);

    for(int i=1;i<=n;i++){

        for(int j=0;j<v[i].size();j++){

            if(v[i][j].w<=lim){

                add(i,v[i][j].x,1);

                add(v[i][j].x,i,1);

            }

        }

    }

    if(Dinic()>=t) return 1;

    else return 0;

}

int main(){

    #ifdef LOCAL

    freopen("in.txt","r",stdin) ;

    freopen("out.txt","w",stdout) ;

    #endif

    scanf("%d%d%d",&n,&m,&t);

    S=1,T=n;

    int l=0,r=1e6+1,M;

    for(int i=0,x,y,z;i<m;i++){

        scanf("%d%d%d",&x,&y,&z);

        v[x].push_back(N(y,z));

    }

    while(r-l>1){

        M=(l+r)>>1;

        if(judge(M)){

            r=M;

        }else l=M;

    }

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

    return 0 ;

}