POJ2112 Optimal Milking---二分+Floyd+网络流

题目链接：

https://vjudge.net/problem/POJ-2112

题目大意：

k个机器，每个机器最多服务m头牛。

c头牛，每个牛需要1台机器来服务。

告诉你牛与机器每个之间的直接距离。

问：让所有的牛都被服务的情况下，使走的最远的牛的距离最短，求这个距离。

解题思路：

二分枚举距离，实际距离满足当前枚举距离限制的可以加入这条边。枚举的距离中符合条件的最小值就是答案。

建图过程：

一个超级汇点，每个机器和汇点的容量都是m。

一个超级源点，和每头牛的容量都是1.

机器i与牛j之间的距离如果小于等于当前枚举值mid，连接i，j，容量1.

这样最大流的意义就是能够服务的牛最多是多少，如果最大流等于牛的总数c，表示当前枚举值mid符合条件，同时说明mid值还可能可以更小，更新二分右边界r = mid .（最终答案也是r不是mid）

如果小于牛的总数，说明mid偏小，更新二分左边界，l = mid + 1.

机器与牛之间的最短距离可以用floyd预处理出来。

  1 #include<iostream>
  2 #include<vector>
  3 #include<cstring>
  4 #include<queue>
  5 using namespace std;
  6 const int maxn = 300 + 10;
  7 const int INF = 0x3f3f3f3f;
  8 struct edge
  9 {
 10     int u, v, c, f;
 11     edge(int u, int v, int c, int f):u(u), v(v), c(c), f(f){}
 12 };
 13 vector<edge>e;
 14 vector<int>G[maxn];
 15 int a[maxn], p[maxn];
 16 void init(int n)
 17 {
 18     e.clear();
 19     for(int i = 0; i <= n; i++)G[i].clear();
 20 }
 21 void addedge(int u, int v, int c)
 22 {
 23     //cout<<u<<" "<<v<<" "<<c<<endl;
 24     e.push_back(edge(u, v, c, 0));
 25     e.push_back(edge(v, u, 0, 0));
 26     int m = e.size();
 27     G[u].push_back(m - 2);
 28     G[v].push_back(m - 1);
 29 }
 30 int Maxflow(int s, int t)
 31 {
 32     int flow = 0;
 33     for(;;)
 34     {
 35         memset(a, 0, sizeof(a));
 36         queue<int>q;
 37         q.push(s);
 38         a[s]  =INF;
 39         while(!q.empty())
 40         {
 41             int u = q.front();
 42             q.pop();
 43             for(int i = 0; i < G[u].size(); i++)
 44             {
 45                 edge& now = e[G[u][i]];
 46                 int v = now.v;
 47                 if(!a[v] && now.c > now.f)//还未流经并且边还有容量
 48                 {
 49                     p[v] = G[u][i];
 50                     a[v] = min(a[u], now.c - now.f);
 51                     q.push(v);
 52                 }
 53             }
 54             if(a[t])break;//已经到达汇点
 55         }
 56         if(!a[t])break;//已经没有增广路
 57         for(int u = t; u != s; u = e[p[u]].u)
 58         {
 59             e[p[u]].f += a[t];
 60             e[p[u] ^ 1].f -= a[t];
 61         }
 62         flow += a[t];
 63     }
 64     return flow;
 65 }
 66 int k, c, m, n;
 67 int s, t;
 68 int Map[maxn][maxn];
 69 void build_map(int Maxdist_min)
 70 {
 71     init(n);//每次构建容量网络清空边
 72     //超级源点s和所有牛建边，权值为1
 73     for(int i = k + 1; i <= n; i++)addedge(s, i, 1);
 74     //所有挤奶机和超级汇点建边，权值为m（也就是一台挤奶机可供牛的最大数目）
 75     for(int i = 1; i <= k; i++)addedge(i, t, m);
 76     for(int i = k + 1; i <= n; i++)//牛的编号，后c个
 77     {
 78         for(int j = 1; j <= k; j++)//挤奶机编号，前k个
 79         {
 80             if(Map[i][j] <= Maxdist_min)//小于最大距离，那么可以直达
 81                 addedge(i, j, 1);//牛和挤奶机可以配对
 82         }
 83     }
 84 }
 85 int main()
 86 {
 87     cin >> k >> c >> m;
 88     n = k + c;
 89     for(int i = 1; i <= n; i++)//前k个点为挤奶机，后c个点为牛
 90     {
 91         for(int j = 1; j <= n; j++)
 92         {
 93             cin >> Map[i][j];
 94             if(Map[i][j] == 0)Map[i][j] = INF;
 95         }
 96     }
 97     //Floyd求最短路
 98     for(int k = 1; k <= n; k++)
 99     {
100         for(int i = 1; i <= n; i++)
101         {
102             for(int j = 1; j <= n; j++)
103             {
104                 Map[i][j] = min(Map[i][j], Map[i][k] + Map[k][j]);
105             }
106         }
107     }
108     int l = 0, r = 10000, mid;//此处最大距离不能是200，题目说的200只是一条边，可能要走很多条边
109     s = 0, t = n + 1;
110     while(l < r)
111     {
112         mid = (l + r) / 2;
113         //cout<<mid<<endl;
114         build_map(mid);
115         if(Maxflow(s, t) >= c)//说明所有的牛已经到达，最大距离可以更小
116             r = mid;
117         else l = mid + 1;
118     }
119     cout<<r<<endl;//最大距离最小,这里的最大距离是r不是mid，因为最后一次循环的时候可能只更新mid和l，没有更新r
120 }