题目大意
有K台挤奶机和C头奶牛，都被视为物体，这K+C个物体之间存在路径。给出一个 (K+C)x(K+C) 的矩阵A，A[i][j]表示物体i和物体j之间的距离，有些物体之间可能没有直接通路。
每台挤奶机可以容纳m头奶牛去挤奶，且每个奶牛仅可以去往一台挤奶机。现在安排这C头奶牛去挤奶，每头奶牛会去往某个挤奶机，求出这C头奶牛去其对应挤奶机的路径长度的最大值的最小值。
题目分析
“每头奶牛仅可以去往一台挤奶机，每台挤奶机最多有M头奶牛”这似乎是一个路径流量的问题，考虑使用网络流算法来解决。
那么，如何确定最长路径的最小值呢？可以先考虑简化问题，“给定一个最大距离L，能否分配这C头奶牛的挤奶机，使得每头奶牛到达挤奶机的距离都小于L”。
解决简化问题：虚拟一个源点和汇点。从源点引出C条容量分别为1的路径到达C头奶牛，再将K台机器分别引出一条容量为M的路径到达汇点。则问题转化为，构造C头奶牛到K台机器的网络路径，且从每头奶牛去往挤奶机的路径的容量为1，距离不超过L，使得网络从源点到汇点的最大流量为C，且C头奶牛走的路径的最大值最小。
然后，再通过二分法枚举最大距离L，找到最大距离的最小值。
具体实现的时候，使用Floyd算法求出奶牛到达挤奶机的最短路径长度；使用ISAP算法找出最大流；使用二分法确定最长的路径最小值。
实现(c++)
#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX_NODE 235
#define MAX_EDGE_NUM 50000
#define INFINITE 1 << 20
#define min(a, b) a < b?a:b
struct Edge{
int from;
int to;
int w;
int next;
int rev;
bool operator==(const pair<int, int>& p){
return from == p.first && to == p.second;
}
};
Edge gEdges[MAX_EDGE_NUM];
int gFlow[MAX_NODE][MAX_NODE];
int gHead[MAX_NODE];
int gDist[MAX_NODE];
int gGap[MAX_NODE];
int gPre[MAX_NODE];
int gPath[MAX_NODE];
int gEdgeCount;
int gSource, gDestination;
void InsertEdge(int u, int v, int w){
Edge* it = find(gEdges, gEdges + gEdgeCount, pair<int, int>(u, v));
if (it != gEdges + gEdgeCount){
it->w = w;
}
else{
int e1 = gEdgeCount++;
gEdges[e1].from = u;
gEdges[e1].to = v;
gEdges[e1].w = w;
gEdges[e1].next = gHead[u];
gHead[u] = e1;
int e2 = gEdgeCount++;
gEdges[e2].from = v;
gEdges[e2].to = u;
gEdges[e2].w = 0;
gEdges[e2].next = gHead[v];
gHead[v] = e2;
gEdges[e1].rev = e2;
gEdges[e2].rev = e1;
}
gFlow[u][v] = w;
}
void Bfs(){
memset(gGap, 0, sizeof(gGap));
memset(gDist, -1, sizeof(gDist));
gDist[gDestination] = 0;
gGap[0] = 1;
queue<int>Q;
Q.push(gDestination);
while (!Q.empty()){
int u = Q.front();
Q.pop();
for (int e = gHead[u]; e != -1; e = gEdges[e].next){
int v = gEdges[e].to;
if (gDist[v] >= 0)
continue;
gDist[v] = gDist[u] + 1;
gGap[gDist[v]] ++;
Q.push(v);
}
}
}
int ISAP(int n){
int e, d, u = gSource;
int ans = 0;
Bfs();
while (gDist[gSource] <= n){
if (u == gDestination){
int min_flow = INFINITE;
for (e = gPath[u]; u != gSource; e = gPath[u = gPre[u]]){
min_flow = min(min_flow, gEdges[e].w);
}
u = gDestination;
for (e = gPath[u]; u != gSource; e = gPath[u = gPre[u]]){
gEdges[e].w -= min_flow;
gEdges[gEdges[e].rev].w += min_flow;
gFlow[gPre[u]][u] -= min_flow;
gFlow[u][gPre[u]] += min_flow;
}
ans += min_flow;
}
for (e = gHead[u]; e != -1; e = gEdges[e].next){
if (gEdges[e].w > 0 && gDist[u] == gDist[gEdges[e].to] + 1)
break;
}
if (e >= 0){
gPre[gEdges[e].to] = u;
gPath[gEdges[e].to] = e;
u = gEdges[e].to;
}
else{
if (--gGap[gDist[u]] == 0)
break;
d = n;
for (int e = gHead[u]; e != -1; e = gEdges[e].next)
if (gEdges[e].w > 0)
d = min(d, gDist[gEdges[e].to]);
gDist[u] = d + 1;
++gGap[gDist[u]];
if (u != gSource)
u = gPre[u];
}
}
return ans;
}
int gMinDist[MAX_NODE][MAX_NODE];
void Floyd(int n){
for (int k = 1; k <= n; k++){
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (gMinDist[i][j] > gMinDist[i][k] + gMinDist[k][j]){
gMinDist[i][j] = gMinDist[i][k] + gMinDist[k][j];
}
}
}
}
}
void BuildGraph(int k, int c, int m, int max_dist){
memset(gHead, -1, sizeof(gHead));
gEdgeCount = 0;
gSource = 0;
gDestination = k + c + 1;
for (int i = k + 1; i <= k + c; i++){
InsertEdge(gSource, i, 1);
}
for (int i = k + 1; i <= k + c; i++){
for (int j = 1; j <= k; j++){
if (gMinDist[i][j] <= max_dist)
InsertEdge(i, j, 1);
}
}
for (int i = 1; i <= k; i++){
InsertEdge(i, gDestination, m);
}
}
void print_graph(int n){
for (int u = 0; u <= n; u++){
printf("node %d links to ", u);
for (int e = gHead[u]; e != -1; e = gEdges[e].next)
printf("%d(flow = %d) ", gEdges[e].to, gEdges[e].w);
printf("
");
}
}
int main(){
int k, c, m, d;
while (scanf("%d %d %d", &k, &c, &m) != EOF){
for (int i = 1; i <= k + c; i++){
for (int j = 1; j <= k + c; j++){
scanf("%d", &gMinDist[i][j]);
if (i != j && gMinDist[i][j] == 0)
gMinDist[i][j] = INFINITE;
}
}
Floyd(k + c);
int beg = 1, end = 40010;
while (beg < end){
int max_dist = (beg + end) / 2;
BuildGraph(k, c, m, max_dist);
// print_graph(k + c + 1);
int max_flow = ISAP(k + c + 2);
if (max_flow == c)
end = max_dist;
else
beg = max_dist + 1;
}
printf("%d
", end);
}
return 0;
}