poj 2112最大流+二分+floyd

やはり図を作るのは難しい.
スーパーソースポイントとスーパーポイントを設定し、スーパーソースポイントから各機械までmであり、乳牛からポイントまで1である.
そしてfloydは機械と乳牛の間の最短ルートを探します
そして、最長距離を二分し、最大流を下にし、流量がcに等しい場合は、下限が見つかるまで二分を続けます.

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <climits>

#include <string>

#include <iostream>

#include <map>

#include <cstdlib>

#include <list>

#include <set>

#include <queue>

#include <stack>

using namespace std;





int Map2[600+2][600+2];

int k,c,m;

int s,e;

int Map[600+2][600+2];

int Min(int a,int b)

{

    return a>b?b:a;

}

int Max;

void  floyd()

{

    Max=0;

    for(int t=1;t<=k+c;t++){

        for(int i=1;i<=k+c;i++)

        for(int j=1;j<=k+c;j++){

           // if(i==j||j==t||t==i) continue;

            Map[i][j]=Min(Map[i][j],Map[i][t]+Map[t][j]);

        }

    }

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

        for(int j=1+k;j<=k+c;j++)

        if(Map[i][j]>Max) Max=Map[i][j];

}



int level[600+2];

const int INF=0xfffffff;

bool bfs()

{

    queue<int> q;

    q.push(s); memset(level,0,sizeof(level)); level[s]=1;

    while(!q.empty()){

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

        for(int i=s;i<=e;i++)

        if(Map2[cur][i]&&!level[i]){

            level[i]=level[cur]+1;

            q.push(i);

        }

    }

    return level[e];

}

int dfs(int x,int val)

{

    int tem=val;

    if(x==e) return val;

    for(int i=s;i<=e&&tem;i++){

        if(Map2[x][i]&&level[i]==level[x]+1){

            int t=dfs(i,Min(tem,Map2[x][i]));

            Map2[x][i]-=t;Map2[i][x]+=t;

            tem-=t;



        }

    }

    return val-tem;

}



void build(int mid)

{

    memset(Map2,0,sizeof(Map2));

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

    Map2[s][i]=m;

    for(int i=k+1;i<=k+c;i++)

        Map2[i][e]=1;

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

        for(int j=k+1;j<=k+c;j++)

        if(Map[i][j]<=mid) Map2[i][j]=1;



}

int erfen()

{

    int mid;

    int l=0;int r=Max;

    //cout<<Max<<endl;system("pause");

    while(l<r){

        mid=(l+r)>>1;

        build(mid);

        int t;int ans=0;

        while(bfs()){

            while(t=dfs(s,INF)) ans+=t;

        }

       // cout<<l<<" "<<r<<" "<<ans<<endl;system("pause");

        if(ans>=c){

            r=mid;

        }

        if(ans<c) l=mid+1;

    }

    return r;

}

int main()

{

    while(scanf("%d%d%d",&k,&c,&m)!=EOF){

        s=0;e=k+c+1;

        memset(Map,0,sizeof(Map));

        for(int i=1;i<=k+c;i++)

        for(int j=1;j<=k+c;j++){

            scanf("%d",&Map[i][j]);

            if(Map[i][j]==0) Map[i][j]=INF;

        }

        floyd();

        cout<<erfen()<<endl;



    }

    return 0;

}