poj2112:http://poj.org/problem?id=2112
题意：K台挤奶机器，C头牛，K不超过30，C不超过200，每台挤奶机器最多可以为M台牛工作，给出这些牛和机器之间，牛和牛之间，机器与机器之间的距离，在保证让最多的牛都有机器挤奶的情况下，给出其中最长的一头牛移动的距离的最小值。
题解：首先用Floyd求出任意两点之间的最短距离，然后再用二分法限定最多的移动距离d，在求最大流时，搜索增广路的时候同时也判断距离有没有超过d就行了。
#include<cstring>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int map[][];
const int INF=;
struct Node{
int c;
int f;
}ma[][];
int m,c,knum,pre[];
int sx,se;
void Floy(){
for(int k=;k<=knum+c;k++)
for(int i=;i<=c+knum;i++)
for(int j=;j<=c+knum;j++){
if(k!=i&&i!=j&&k!=j&&map[i][k]+map[k][j]<map[i][j])
map[i][j]=map[i][k]+map[k][j];
}
}
bool BFS(){
memset(pre,,sizeof(pre));
queue<int>Q;
Q.push(sx);
pre[sx]=;
while(!Q.empty()){
int d=Q.front();
Q.pop();
for(int i=;i<=knum+c+;i++){
if(!pre[i]&&ma[d][i].c-ma[d][i].f){
pre[i]=pre[d]+;
Q.push(i);
}
}
}
return pre[se]!=;
}
int dinic(int pos,int flow){
int f=flow;
if(pos==se)
return flow;
for(int i=;i<=c+knum+;i++){
if(ma[pos][i].c-ma[pos][i].f&&pre[i]==pre[pos]+){
int a=ma[pos][i].c-ma[pos][i].f;
int t=dinic(i,min(a,flow));
ma[pos][i].f+=t;
ma[i][pos].f-=t;
flow-=t;
if(flow<=)break;
}
}
if(f-flow<=)pre[pos]=-;
return f-flow;
}
int sum(){
int s=;
while(BFS())
s+=dinic(sx,INF);
return s;
}
void build(int maxn){
memset(ma,,sizeof(ma));
for(int i=knum+;i<=knum+c;i++)
ma[][i].c=;
for(int i=;i<=knum;i++)
ma[i][se].c=m;
for(int i=knum+;i<=c+knum;i++)
for(int j=;j<=knum;j++){
if(map[i][j]<=maxn)
ma[i][j].c=;
}
}
int dinic2(int maxn) {
int maxflow;
int low=,mid,up=maxn;
while(low<=up){
mid=(low+up)>>;
build(mid);
maxflow=;
maxflow=sum();
if(maxflow<c)low=mid+;
else
up=mid-;
}
return up+;
}
int main(){
int maxn;
while(~scanf("%d%d%d",&knum,&c,&m)){
sx=;se=knum+c+;
maxn=;
for(int i=;i<=knum+c;i++)
for(int j=;j<=knum+c;j++){
scanf("%d",&map[i][j]);
if(map[i][j]==)
map[i][j]=INF;
}
Floy();
for(int i=;i<=knum+c;i++)
for(int j=;j<=knum+c;j++)
if(map[i][j]<INF&&map[i][j]>maxn)
maxn=map[i][j]; printf("%d\n",dinic2(maxn)); }
}