Optimal Milking
Description
FJ
has moved his K (1 <= K <= 30) milking machines out into the cow
pastures among the C (1 <= C <= 200) cows. A set of paths of
various lengths runs among the cows and the milking machines. The
milking machine locations are named by ID numbers 1..K; the cow
locations are named by ID numbers K+1..K+C.
Each milking point can "process" at most M (1 <= M <= 15) cows each day.
Write a program to find an assignment for each cow to some milking
machine so that the distance the furthest-walking cow travels is
minimized (and, of course, the milking machines are not overutilized).
At least one legal assignment is possible for all input data sets. Cows
can traverse several paths on the way to their milking machine.
Input
* Line 1: A single line with three space-separated integers: K, C, and M.
* Lines 2.. ...: Each of these K+C lines of K+C space-separated
integers describes the distances between pairs of various entities. The
input forms a symmetric matrix. Line 2 tells the distances from milking
machine 1 to each of the other entities; line 3 tells the distances
from machine 2 to each of the other entities, and so on. Distances of
entities directly connected by a path are positive integers no larger
than 200. Entities not directly connected by a path have a distance of
0. The distance from an entity to itself (i.e., all numbers on the
diagonal) is also given as 0. To keep the input lines of reasonable
length, when K+C > 15, a row is broken into successive lines of 15
numbers and a potentially shorter line to finish up a row. Each new row
begins on its own line.
Output
A single line with a single integer that is the minimum possible total distance for the furthest walking cow.
Sample Input
2 3 2
0 3 2 1 1
3 0 3 2 0
2 3 0 1 0
1 2 1 0 2
1 0 0 2 0
Sample Output
2
題意：有k個牛奶機跟c頭牛。他們之間有路相連，農民想讓每個牛能到其中一個牛奶機，又想讓最累的牛累的程度最小。
分析：本來傻傻的用費用流，但發現不對，因為每個增廣路不是單純的一個牛走的路，會包含其他牛走過的路在里面，詳細另一篇關于最大流的歸納。
這個題是求牛走的最長路，那枚舉ans，然后對牛到奶牛機的最短距離滿足ans的連一條容量inf的邊，如果最大流等于牛的數量，則ans是合法的。
二分最大流代碼：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define Min(a, b) (a) < (b) ? a : b
using namespace std;
const int MAXN = 1005;
const int MAXM = 210000;
const int INF = 1000000000;
struct Edge
{
int st, ed;
int next;
int flow;
int cap;
}edge[MAXM];
int head[MAXN], level[MAXN], E, map[MAXN][MAXN];
void add(int u, int v, int w)
{
//printf("add %d %d %d\n", u, v, w);
edge[E].flow = 0;
edge[E].cap = w;
edge[E].st = u;
edge[E].ed = v;
edge[E].next = head[u];
head[u] = E++;
edge[E].flow = 0;
edge[E].cap = 0;
edge[E].st = v;
edge[E].ed = u;
edge[E].next = head[v];
head[v] = E++;
}
int dinic_bfs(int src, int dest, int ver)
{
int i, j;
for (i = 0; i <= ver; i++)
{
level[i] = -1;
}
int que[MAXN], rear = 1;
que[0] = src; level[src] = 0;
for(i = 0; i < rear; i++)
{
for(j = head[que[i]]; j != -1; j = edge[j].next)
{
if(level[edge[j].ed] == -1 && edge[j].cap > edge[j].flow)
{
level[edge[j].ed] = level[que[i]]+1;
que[rear++] = edge[j].ed;
}
}
}
return level[dest] >= 0;
}
int dinic_dfs(int src, int dest, int ver)
{
int stk[MAXN], top = 0;
int ret = 0, cur, ptr, pre[MAXN], minf, i;
int del[MAXN];
for (i = 0; i <= ver; i++)
{
del[i] = 0;
}
stk[top++] = src;
pre[src] = src;
cur = src;
while(top)
{
while(cur != dest && top)
{
for(i = head[cur]; i != -1; i = edge[i].next)
{
if(level[edge[i].ed] == level[cur] + 1 && edge[i].cap > edge[i].flow && !del[edge[i].ed])
{
stk[top++] = edge[i].ed;
cur = edge[i].ed;
pre[edge[i].ed] = i;
break;
}
}
if(i == -1)
{
del[cur] = 1;
top--;
if(top) cur = stk[top-1];
}
}
if(cur == dest)
{
minf = INF;
while(cur != src)
{
cur = pre[cur];
if(edge[cur].cap - edge[cur].flow < minf) minf = edge[cur].cap - edge[cur].flow;
cur = edge[cur].st;
}
cur = dest;
while(cur != src)
{
cur = pre[cur];
edge[cur].flow += minf;
edge[cur^1].flow -= minf;
if(edge[cur].cap - edge[cur].flow == 0)
{
ptr = edge[cur].st;
}
cur = edge[cur].st;
}
while(top > 0&& stk[top-1] != ptr) top--;
if(top) cur = stk[top-1];
ret += minf;
}
}
return ret;
}
int Dinic(int src, int dest, int ver)
{
int ret = 0, t;
while(dinic_bfs(src, dest, ver))
{
t = dinic_dfs(src, dest, ver);
if(t) ret += t;
else break;
}
return ret;
}
void floyd(int n)//每個點的最近距離,這個不多說了。保證map[i][k]跟map[k][j]都以存在就行
{
int k, i, j;
for (k = 1; k <= n; k++)//k表示中間點，一定放在最外面
{
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
if (i != j && map[i][k] != INF && map[k][j] != INF && map[i][k] + map[k][j] < map[i][j])
{
map[i][j] = map[i][k] + map[k][j];
}
}
}
}
}
void build(int distance, int k, int c, int m)
{
int n = c + k, i, j;
E = 0;
for (i = 0; i <= n + 1; i++)
{
head[i] = -1;
}
for (i = k + 1; i <= n; i++)
{
add(0, i, 1);//源到牛的容量是1 ，題目是要求每只牛都能去任意一個奶牛機就行了
for (j = 1; j <= k; j++)
{
if (map[i][j] <= distance)//對滿足距離的兩個點牛跟牛奶機
{
add(i, j, INF);//牛到牛奶機的容量inf
}
}
}
for (j = 1; j <= k; j++)//牛奶機到匯的容量為m
{
add(j, n + 1, m);
}
}
int main()
{
int c, k, m, n, i, j;
scanf("%d%d%d", &k, &c, &m);
n = c + k;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
{
scanf("%d", &map[i][j]);
if (map[i][j] == 0)
{
map[i][j] = INF;
}
}
}
floyd(n);
int l = 0, r = INF - 10, mid, ans;
int s = 0, t = c + k + 1, ver = t + 1;
while (l < r)//因為二分出現l+1=r的時候，(l+r) >> 1 = l的。所以l+1就等于r了，當l跟r相等的時候就是解
{
mid = (l + r) >> 1;
build(mid, k, c, m);
ans = Dinic(0, t, ver);
if (ans == c)
{
r = mid;//r是保證能滿足最大流等于牛的數量
}
else
{
l = mid + 1;
}
}
printf("%d\n", r);
return 0;
}
/*
2 3 2
0 3 2 1 1
3 0 3 2 0
2 3 0 1 0
1 2 1 0 2
1 0 0 2 0
1 1 1
0 1
1 0
2 2 1
0 0 1 3
0 0 2 100
1 2 0 0
3 100 0 0
*/