poj2112Optimal Milking(最優秀的擠奶方案)——floyd+最大流+二分

poj2112Optimal Milking(最優秀的擠奶方案)——floyd+最大流+二分

題目描述：
農場主John 將他的K(1≤K≤30)個擠奶器運到牧場，在那裡有C(1≤C≤200)頭奶牛，在奶
牛和擠奶器之間有一組不同長度的路。K個擠奶器的位置用1～K的編號標明，奶牛的位置用K+1～
K+C 的編號標明。
每台擠奶器每天最多能為M(1≤M≤15)頭奶牛擠奶。
編寫程序，尋找一個方案，安排每頭奶牛到某個擠奶器擠奶，並使得C 頭奶牛需要走的所有
路程中的最大路程最小。每個測試數據中至少有一個安排方案。每條奶牛到擠奶器有多條路。

輸入描述：
測試數據的格式如下：
第1 行為3 個整數K、C 和M。
第2～K+C+1 行，每行有K+C 個整數，描述了奶牛和擠奶器（二者合稱實體）之間的位置，
這K+C 行構成了一個沿對角線對稱的矩陣。第2 行描述了第1 個擠奶器離其他實體的距離，…，
第K+1 行描述了第K 個擠奶器離其他實體的距離；第K+2 行描述了第1 頭奶牛離其他實體的距
離，…。這些距離為不超過200 的正數。實體之間如果沒有直接路徑相連，則距離為0。實體與
本身的距離（即對角線上的整數）也為0。

輸出描述：
輸出一個整數，為所有方案中，C 頭奶牛需要走的最大距離的最小值。

因為題目要求路徑裡面最大的最小，所以先用floyd求得任意兩點之間的最短路，然後二分枚舉可能的最大邊，根據所枚舉的最大邊的前提限制，建圖，源點到各個奶牛的容量為1，各個牛奶站到匯點的容量為M，如果某個奶牛到奶牛站的距離小於等於所枚舉的最大邊，則容量為1，求得最大流是否等於C

#include
#include
#include
#include
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i,a,b) for(int i=(a);i<=(b);++i)
const int maxn=250;
const int INF=1<<30;
using namespace std;
int n,s,t;
int K,C,M;
struct Edge{
    int from,to,cap,flow;
    Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
vector edges;
vector G[maxn];
int gap[maxn],d[maxn],cur[maxn],p[maxn];
inline void addedge(int u,int v,int c){
    edges.push_back(Edge(u,v,c,0));
    edges.push_back(Edge(v,u,0,0));
    int m=edges.size();
    G[u].push_back(m-2);
    G[v].push_back(m-1);
}
int ISAP(){
    s=0,t=n;
    memset(cur,0,sizeof(cur));
    memset(d,0,sizeof(d));
    memset(gap,0,sizeof(gap));
    int x=s,flow=0,a=INF;
    while(d[s]e.flow&&d[e.to]+1==d[x]){
                p[e.to]=G[x][i];
                cur[x]=i;
                x=e.to;
                ok=1;
                a=min(a,e.cap-e.flow);
                break;
            }
        }
        if(!ok){
            int m=n;
            for(int i=0;ie.flow) m=min(m,d[e.to]);
            }
            if(--gap[d[x]]==0) break;
            gap[d[x]=m+1]++;
            cur[x]=0;
            if(x!=s) x=edges[p[x]].from;
        }
    }
    return flow;
}



int g[maxn][maxn];
int maxh,maxedge;
void floyd(){
    maxh=-1;
    FORD(k,1,n)FORD(i,1,n){
        if(g[i][k]>K>>C>>M;
    n=K+C;
    FORD(i,1,n)FORD(j,1,n){
        scanf(%d,&g[i][j]);
        if(g[i][j]==0) g[i][j]=INF;
    }
    floyd();
    n+=2;
    int maxflow;
    int l=0,r=maxh;
    while(l>1;
        build(mid);
        maxflow=ISAP();
        cout<=C) r=mid;
        else l=mid+1;
    }
    build(r);
    cout<