Optimal Milking poj2112 二分+最大流

Description

---

K个产奶机，C头奶牛，且每个产奶机最多可供M头奶牛使用；已知奶牛之间的两两距离，求如何安排使得在任何一头奶牛都有自己产奶机的条件下，奶牛到产奶机的最远距离最短？最短是多少？

Solution

---

看到最大值最小就要想到二分答案了

先floyd求两两之间最短路，二分的时候上界直接粗暴地用INF，或者别的什么也行

机器和牛棚分别连向源点和汇点，其中机器的限制m作为源点连向机器的容量

Code

---

#include <stdio.h> #include <string.h> #include <queue> #define rep(i, st, ed) for (int i = st; i <= ed; i += 1) #define erg(i, now) for (int i = ls[now]; i; i = e[i].next) #define fill(x, t) memset(x, t, sizeof(x)) #define INF 0x3f3f3f3f #define N 531 #define E N * N / 2 + 1 struct edge{int x, y, w, next;}e[E]; int rc[N][N], dis[N], ls[N]; inline void addEdge(int &cnt, int x, int y, int w){ e[++ cnt] = (edge){x, y, w, ls[x]}; ls[x] = cnt; e[++ cnt] = (edge){y, x, 0, ls[y]}; ls[y] = cnt; } using std:: queue; inline int bfs(int st, int ed){ fill(dis, -1); dis[st] = 1; queue<int> q; q.push(st); while (!q.empty()){ int now = q.front(); q.pop(); erg(i, now){ if (e[i].w > 0 && dis[e[i].y] == -1){ q.push(e[i].y); dis[e[i].y] = dis[now] + 1; if (e[i].y == ed){ return 1; } } } } return 0; } inline int min(int x, int y){ return x<y?x:y; } inline int find(int now, int ed, int mn){ if (now == ed || !mn){ return mn; } int ret = 0; erg(i, now){ if (e[i].w > 0 && dis[now] + 1 == dis[e[i].y]){ int d = find(e[i].y, ed, min(mn - ret, e[i].w)); e[i].w -= d; e[i ^ 1].w += d; ret += d; if (ret == mn){ break; } } } return ret; } inline int dinic(int st, int ed){ int mxFlow = 0; while (bfs(st, ed)){ mxFlow += find(st, ed, INF); } return mxFlow; } inline int cheque(int lim, int k, int c, int m){ int st = 0, ed = N - 1; int edgeCnt = 1; fill(ls, 0); rep(i, 1, k){ rep(j, k + 1, k + c){ if (rc[i][j] <= lim){ addEdge(edgeCnt, i, j, 1); } } } rep(i, 1, k){ addEdge(edgeCnt, st, i, m); } rep(i, k + 1, k + c){ addEdge(edgeCnt, i, ed, 1); } int mxFlow = dinic(st, ed); return mxFlow; } int main(void){ int p, c, m; scanf("%d%d%d", &p, &c, &m); rep(i, 1, p + c){ rep(j, 1, p + c){ scanf("%d", &rc[i][j]); if (!rc[i][j]){ rc[i][j] = INF; } } } rep(k, 1, p + c){ rep(i, 1, p + c){ rep(j, 1, p + c){ if (i != j && j != k && i != k && rc[i][k] + rc[k][j] < rc[i][j]){ rc[i][j] = rc[i][k] + rc[k][j]; } } } } int l = 0, r = INF - 1; int ans = 0; while (l <= r){ int mid = (l + r) >> 1; int mxFlow = cheque(mid, p, c, m); if (mxFlow >= c){ ans = mid; r = mid - 1; }else{ l = mid + 1; } } PRintf("%d\n", ans); return 0; }