1 #include 
     
        2 #include 
      
         3 const int MAXN=250;//点数的最大值  4 const int MAXM=12500;//边数的最大值  5 const int INF=0x3fffffff;  6   7 struct Node  8 {  9     int from,to,next; 10     int cap; 11 }edge[MAXM]; 12  13 int tol; 14 int head[MAXN]; 15 int dep[MAXN]; 16 int gap[MAXN];//gap[x]=y :说明残留网络中dep[i]==x的个数为y 17 int matrix[250][250]; 18 int n;//n是总的点的个数，包括源点和汇点 19  20 void init() 21 { 22     tol=0; 23     memset(head,-1,sizeof(head)); 24 } 25  26 void addedge(int u,int v,int w) 27 { 28     edge[tol].from=u; 29     edge[tol].to=v; 30     edge[tol].cap=w; 31     edge[tol].next=head[u]; 32     head[u]=tol++; 33     edge[tol].from=v; 34     edge[tol].to=u; 35     edge[tol].cap=0; 36     edge[tol].next=head[v]; 37     head[v]=tol++; 38 } 39 void BFS(int start,int end) 40 { 41     memset(dep,-1,sizeof(dep)); 42     memset(gap,0,sizeof(gap)); 43     gap[0]=1; 44     int que[MAXN]; 45     int front,rear; 46     front=rear=0; 47     dep[end]=0; 48     que[rear++]=end; 49     while(front!=rear) 50     { 51         int u=que[front++]; 52         if(front==MAXN)front=0; 53         for(int i=head[u];i!=-1;i=edge[i].next) 54         { 55             int v=edge[i].to; 56             if(dep[v]!=-1)continue; 57             que[rear++]=v; 58             if(rear==MAXN)rear=0; 59             dep[v]=dep[u]+1; 60             ++gap[dep[v]]; 61         } 62     } 63 } 64 int SAP(int start,int end) 65 { 66     int res=0; 67     BFS(start,end); 68     int cur[MAXN]; 69     int S[MAXN]; 70     int top=0; 71     memcpy(cur,head,sizeof(head)); 72     int u=start; 73     int i; 74     while(dep[start]
       
        edge[S[i]].cap) 82                { 83                    temp=edge[S[i]].cap; 84                    inser=i; 85                } 86             for(i=0;i
        
         dep[edge[i].to])113                 {114                     min=dep[edge[i].to];115                     cur[u]=i;116                 }117             }118             --gap[dep[u]];119             dep[u]=min+1;120             ++gap[dep[u]];121             if(u!=start)u=edge[S[--top]].from;122         }123     }124     return res;125 }126 void floyd(int matrix[250][250],int n)127 {128     for(int k = 1;k <= n;k++)129     {130         for(int i = 1;i <= n;i++)131         {132             for(int j = 1;j <= n;j++)133             {134                 if(matrix[i][j] > matrix[i][k] + matrix[k][j])135                 {136                     matrix[i][j] = matrix[i][k] + matrix[k][j];137                 }138             }139         }140     }141 }142 int main()143 {144     int k,c,m;145     while(~scanf("%d%d%d",&k,&c,&m))146     {147         for(int i = 1;i <= k + c;i++)148         {149             for(int j = 1;j <= k + c;j++)150             {151                 scanf("%d",&matrix[i][j]);152                 if(matrix[i][j] == 0 && i != j)153                 {154                     matrix[i][j] =INF;155                 }156             }157         }158         floyd(matrix,k + c);159         int ans = 0;160         for(int i = k + 1;i <= k + c;i++)161         {162             for(int j = 1;j <= k;j++)163             {164                 if(matrix[i][j] > ans)165                 {166                     ans = matrix[i][j];167                 }168             }169         }170         int s = 0,t = k + c + 1;171         n = k + c + 2;172         int right = ans,left = 0;173         while(left + 1 < right)174         {175             int mid = (left + right) / 2;176             init();177             for(int i = k + 1;i <= k + c;i++)178             {179                 addedge(s,i,1);180                 for(int j = 1;j <= k;j++)181                 {182                     if(matrix[i][j] <= mid)183                     {184                         addedge(i,j,1);185                     }186                 }187             }188             for(int j = 1;j <= k;j++)189             {190                 addedge(j,t,m);191             }192             if(SAP(s,t) == c)193             {194                 right = mid;195             }196             else197             {198                 left = mid;199             }200         }201         printf("%d\n",right);202     }203     return 0;204 }
        
       
      
     

 

题意:给出奶牛、机器之间的距离（包括奶牛-奶牛距离，机器-机器距离，奶牛-机器距离），以及机器的处理奶牛的最大数量，求走得最远的奶牛可以走的最近距离。

分析：源点构造边，指向每一个奶牛顶点，容量为1（因为每个顶点的奶牛数量都是1），然后二分法枚举最短的距离，奶牛-机器距离不大于限定的距离的建一条由奶牛指向机器的边，容量为1，每个机器都建一条指向汇点的边，容量为m.