Optimal Milking

题意：K台挤奶机器，C头牛，K不超过30，C不超过200，每台挤奶机器最多可以为M台牛工作，给出这些牛和机器之间，牛和牛之间，机器与机器之间的距离，在保证让最多的牛都有机器挤奶的情况下，给出其中最长的一头牛移动的距离的最小值。

题解：首先用Floyd求出任意两点之间的最短距离，然后再用二分法限定最多的移动距离d，在求最大流时，搜索增广路的时候同时也判断距离有没有超过d就行了。

  1 #include<cstring>
  2 #include<iostream>
  3 #include<cstdio>
  4 #include<algorithm>
  5 #include<queue>
  6 using namespace std;
  7 int map[301][301];
  8 const int INF=100000000;
  9 struct Node{
 10     int c;
 11     int f;
 12 }ma[301][301];
 13 int m,c,knum,pre[301];
 14 int sx,se;
 15 void Floy(){
 16     for(int k=1;k<=knum+c;k++)
 17        for(int i=1;i<=c+knum;i++)
 18            for(int j=1;j<=c+knum;j++){
 19                if(k!=i&&i!=j&&k!=j&&map[i][k]+map[k][j]<map[i][j])
 20                    map[i][j]=map[i][k]+map[k][j];
 21            }
 22 }
 23 bool  BFS(){
 24     memset(pre,0,sizeof(pre));
 25     queue<int>Q;
 26     Q.push(sx);
 27     pre[sx]=1;
 28     while(!Q.empty()){
 29         int d=Q.front();
 30         Q.pop();
 31         for(int i=0;i<=knum+c+1;i++){
 32             if(!pre[i]&&ma[d][i].c-ma[d][i].f){
 33             pre[i]=pre[d]+1;
 34             Q.push(i);
 35             }
 36         }
 37     }
 38     return pre[se]!=0;
 39 }
 40 int dinic(int pos,int flow){
 41     int f=flow;
 42      if(pos==se)
 43        return flow;
 44      for(int i=0;i<=c+knum+1;i++){
 45            if(ma[pos][i].c-ma[pos][i].f&&pre[i]==pre[pos]+1){
 46                 int a=ma[pos][i].c-ma[pos][i].f;
 47                 int t=dinic(i,min(a,flow));
 48                 ma[pos][i].f+=t;
 49                 ma[i][pos].f-=t;
 50                 flow-=t;
 51                 if(flow<=0)break;
 52                 }
 53        }
 54        if(f-flow<=0)pre[pos]=-1;
 55     return f-flow;
 56 }
 57 int sum(){
 58      int s=0;
 59     while(BFS())
 60        s+=dinic(sx,INF);
 61        return s;
 62 }
 63 void build(int maxn){
 64     memset(ma,0,sizeof(ma));
 65    for(int i=knum+1;i<=knum+c;i++)
 66          ma[0][i].c=1;
 67    for(int i=1;i<=knum;i++)
 68          ma[i][se].c=m;
 69    for(int i=knum+1;i<=c+knum;i++)
 70        for(int j=1;j<=knum;j++){
 71               if(map[i][j]<=maxn)
 72                   ma[i][j].c=1;
 73            }
 74 }
 75 int dinic2(int maxn) {
 76     int maxflow;
 77     int low=0,mid,up=maxn;
 78     while(low<=up){
 79         mid=(low+up)>>1;
 80        build(mid);
 81         maxflow=0;
 82        maxflow=sum();
 83         if(maxflow<c)low=mid+1;
 84         else
 85             up=mid-1;
 86     }
 87     return up+1;
 88 }
 89 int main(){
 90     int maxn;
 91     while(~scanf("%d%d%d",&knum,&c,&m)){
 92         sx=0;se=knum+c+1;
 93         maxn=0;
 94         for(int i=1;i<=knum+c;i++)
 95           for(int j=1;j<=knum+c;j++){
 96                scanf("%d",&map[i][j]);
 97                if(map[i][j]==0)
 98                   map[i][j]=INF;
 99           }
100              Floy();
101           for(int i=1;i<=knum+c;i++)
102             for(int j=1;j<=knum+c;j++)
103                if(map[i][j]<INF&&map[i][j]>maxn)
104                    maxn=map[i][j];
105 
106              printf("%d
",dinic2(maxn));
107 
108         }
109 }

View Code