poj 2112最佳擠奶方案

[cpp] 
用FLOYD求出任意兩點最小距離，用Dinic求最大流，用二分法搜索最大距離最小值 
#include <iostream>  
#include <cstring>  
#include <cstdio>  
using namespace std; 
 
#define MAX 300  
#define INF 1000000  
int dis[MAX][MAX]; 
int map[MAX][MAX]; 
 
bool sign[MAX][MAX]; 
bool used[MAX]; 
int K,C,n,M; 
 
int min(int a,int b) 
{ 
  return a < b ? a : b; 
} 
 
void Build_Graph(int min_max) 
{ 
  int i,j; 
  memset(map,0,sizeof(map)); 
  for(i = K+1; i <=n; i++)   //從源點向每頭奶牛建一條邊，容量為1  
    map[0][i] = 1; 
  for(i = 1; i <= K; i++)    //從取奶器向匯點建邊，容量為M  
    map[i][n+1] = M; 
  for(i = K+1;i <= n;i++) //從每頭奶牛向取奶器建邊，容量為1  
    { 
      for(j = 1; j <= K;j++) 
    { 
      if(dis[i][j] <= min_max) 
        map[i][j] = 1; 
    } 
    } 
} 
 
bool BFS()  //構建層次網絡  
{ 
  memset(used,0,sizeof(used)); 
  memset(sign,0,sizeof(sign)); 
  int queue[100*MAX] = {0}; 
  queue[0] = 0; 
  used[0] = 1; 
  int t = 1,f = 0; 
  while(f < t) 
    { 
      for(int i = 0; i <= n + 1; i++) 
    { 
      if(!used[i] && map[queue[f]][i]) 
        { 
          queue[t++] = i; 
          used[i] = 1; 
          sign[queue[f]][i] = 1; 
        } 
    } 
      f++; 
    } 
  if(used[n+1]) 
    return true; 
  else 
    return false; 
} 
 
int DFS(int v,int sum)  //DFS增廣  
{ 
  int i,s,t; 
  if(v == n + 1) 
    return sum; 
  s = sum; 
  for(i = 0; i <= n+1;i++) 
    { 
      if(sign[v][i]) 
    { 
      t = DFS(i,min(map[v][i],sum)); 
      map[v][i] -= t; 
      map[i][v] += t; 
      sum -= t; 
    } 
    } 
  return s-sum; 
} 
 
int main() 
{ 
  int i,j,k,L,R,mid,ans; 
  cin>>K>>C>>M; 
  n = K + C; 
  for(i = 1; i <= n; i++) 
    { 
      for(j = 1; j <= n; j++) 
    { 
      cin>>dis[i][j]; 
      if(dis[i][j] == 0) 
        dis[i][j] = INF; 
    } 
    } 
  for(k = 1; k <= n; k++)  //floyd求最短距離  
    for(i = 1; i <= n; i++) 
      for(j = 1; j <= n; j++) 
    { 
      dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]); 
    } 
  L = 0, R = 10000; 
  while(L < R)  //二分搜索  
    { 
      mid = (L + R)/2; 
      ans = 0; 
      Build_Graph(mid); 
      while(BFS()) ans += DFS(0,INF);   //dinic求最大流  
      if(ans >= C) R = mid; 
      else L = mid + 1; 
    } 
  cout<<R<<endl; 
  return 0;