POJ 2112 Optimal Milking dinic算法网络流+二分

思路就是先用floyd算出奶牛到挤奶器的最短距离，然后二分查找最大距离的最小值，构造出满足任何奶牛到挤奶器的距离都小于该最小值的网络流，求一个最大流，如果该值等于奶牛的数目，就是可行方案，然后最小值还可以少点，如果不可行，最小值得增大。加入超源点与超收点，超源点到每头奶牛建边，容量为1，每个挤奶器到超收点建边，容量为m。其实这题用二分匹配判可行会更好。

求网络的最大流用的是dinic算法，不太理解，抄的书上的代码。

以下为代码：

View Code

  1 #include <cstdio>
  2 #include <cstring>
  3 #define INF 300000000
  4 #define MAXN 300
  5 int k,c,m,n;//k个挤奶器，c头奶牛，挤奶器的容量
  6 int dis[MAXN][MAXN];
  7 int map[MAXN][MAXN];  //容量网络
  8 int sign[MAXN][MAXN];//层次网络
  9 int min(int x,int y)
 10 {
 11     if(x < y)
 12         return x;
 13     else
 14         return y;
 15 }
 16 void Floyd()
 17 {
 18     int i,j;
 19     //读入数据
 20     scanf("%d%d%d",&k,&c,&m);
 21     n = k+c;
 22     for(i=1; i<=n; ++i)//初始化距离矩阵
 23     {
 24         for(j=1; j<=n ; ++j)
 25         {
 26             scanf("%d",&dis[i][j]);
 27             if(dis[i][j] == 0) dis[i][j] = INF;
 28         }
 29     }
 30     //floyd求任意两点间的最小距离
 31     for(int g=1; g<=n; ++g)
 32     {
 33         for(i=1; i<=n; ++i)
 34         {
 35             for(j=1; j<=n; ++j)
 36             {
 37                 int t =dis[i][g] + dis[g][j] ;
 38                 if(t < dis[i][j])
 39                     dis[i][j] = t;
 40             }
 41         }
 42     }
 43 }
 44 //构造出最大路程为 x的图
 45 void Build(int x)
 46 {
 47     int i,j;
 48     memset(map,0,sizeof(map));
 49     for(i=k+1; i<=n; ++i)//超源点到每头奶牛的容量为1
 50         map[0][i] = 1;
 51     for(i=1; i<=k ; ++i)//每个挤奶器到超收点的容量为m，表明每个挤奶器最多只能给m头奶牛挤奶
 52         map[i][n+1] = m;
 53     for(i=k+1; i<=n; ++i)
 54     {
 55         for(j = 1; j<=k; j++)
 56         {
 57             if(dis[i][j] <= x) map[i][j] = 1;//如果该奶牛到挤奶器的距离小于等于x（最大距离），允许该奶牛去该挤奶器
 58         }
 59     }
 60 }
 61 //构造层次网络
 62 bool BFS()
 63 {
 64     int queue[MAXN];
 65     bool used[MAXN];
 66     memset(used,0,sizeof(used));
 67     memset(sign,0,sizeof(sign));
 68     used[0] = 1;
 69     int fr=0,ta=0;
 70     queue[ta++] = 0;
 71     while(fr != ta)
 72     {
 73         int v = queue[fr++];
 74         for(int i=0; i<= n+1; ++i)
 75         {
 76             if(!used[i] && map[v][i])//
 77             {
 78                 queue[ta++] = i;
 79                 used[i] = 1;
 80                 sign[v][i] = 1;
 81             }
 82         }
 83     }
 84     return used[n+1];//used[n+1]为true,超收点在层次网络中，为false,不在层次网络中，这时已经找不到增广路了
 85 }
 86 int DFS(int v,int sum)//并不是很理解
 87 {
 88     int i,s,t;
 89     if(v == n+1) return sum;//到了超收点，返回调整量sum.
 90     s = sum;
 91     for(i=0; i<=n+1; ++i)
 92     {
 93         if(sign[v][i])
 94         {
 95             t = DFS(i,min(map[v][i],sum));//沿着一条路搜下去
 96             map[v][i] -= t;//减去调整量
 97             map[i][v] += t;//反方向的边加上调整量
 98             sum -= t;
 99         }
100     }
101     return s-sum;
102 }
103 int main()
104 {
105 //    freopen("in.cpp","r",stdin);
106     Floyd();
107     int l = 0,r = 10000;
108     while(l <r)//二分查找最大距离的最小值
109     {
110         int mid = (l+r)/2;
111         int ans = 0;
112         // dinic算法
113         Build(mid);
114         while(BFS()) ans += DFS(0,INF);//ans为最后超收点接收到的奶牛数
115         if(ans >= c) r = mid;//如果大于 c ,证明该最小值还能小点，否则只能大点
116         else l = mid+1;
117     }
118     printf("%d\n",r);
119     return 0;
120 }

POJ 2112 Optimal Milking dinic算法 网络流+二分

POJ 2112 Optimal Milking dinic算法网络流+二分