<题目链接>
题目大意：
有K台挤奶机和C头奶牛，都被视为物体，这K+C个物体之间存在路径。给出一个 (K+C)x(K+C) 的矩阵A，A[i][j]表示物体i和物体j之间的距离，有些物体之间可能没有直接通路。 每台挤奶机可以容纳m头奶牛去挤奶，且每个奶牛仅可以去往一台挤奶机。现在安排这C头奶牛去挤奶，每头奶牛会去往某个挤奶机，求出这C头奶牛去其挤奶的最长路径的最小值。
解题分析：
因为要求最长路径的最小值，所以我们很容易想到二分答案。由于数据量较小，所以我们先用floyed求出所有点之间的最短距离，然后直接二分答案，枚举最长路径的最小值，再根据枚举的值建图，源点向所有机器连一条容量为m的边，所有的牛向汇点连一条容量为1的边，并且距离<=枚举值的机器与牛连一条容量为1的边，最后求最大流，如果最大流==c，则成立。
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std; #define rep(i,s,t) for(int i=s;i<=t;i++)
typedef long long LL;
const int MX = ;
const int MXE = * MX * MX;
const LL INFLL = 0x3f3f3f3f3f3f3f3fLL;
const int INF = 0x3f3f3f3f;
int mp[][];
int k, c, m,maxdist;
struct MaxFlow {
struct Edge {
int v, nxt;
LL w;
} E[MXE];
int tot, num, s, t;
int head[MX];
void init() {
memset (head, -, sizeof (head) );
tot = ;
}
void add (int u, int v, LL w) {
E[tot].v=v,E[tot].nxt=head[u],E[tot].w=w;
head[u] = tot++; E[tot].v=u,E[tot].nxt=head[v],E[tot].w=;
head[v] = tot++;
}
int d[MX], vis[MX], gap[MX];
void bfs() {
memset (d, , sizeof (d) );
memset (gap, , sizeof (gap) );
memset (vis, , sizeof (vis) );
queue<int>q;
q.push (t);
vis[t] = ;
while (!q.empty() ) {
int u = q.front();
q.pop();
for (int i = head[u]; ~i; i = E[i].nxt) {
int v = E[i].v;
if (!vis[v]) {
d[v] = d[u] + ;
gap[d[v]]++;
q.push (v);
vis[v] = ;
}
}
}
}
int last[MX];
LL dfs (int u, LL f) {
if (u == t) return f;
LL sap = ;
for (int i = last[u]; ~i; i = E[i].nxt) {
int v = E[i].v;
if (E[i].w > && d[u] == d[v] + ) {
last[u] = i;
LL tmp = dfs (v, min (f - sap, E[i].w) );
E[i].w -= tmp;
E[i ^ ].w += tmp;
sap += tmp;
if (sap == f) return sap;
}
}
if (d[s] >= num) return sap;
if (! (--gap[d[u]]) ) d[s] = num;
++gap[++d[u]];
last[u] = head[u];
return sap;
}
LL solve (int st, int ed, int n) {
LL flow = ;
num = n;s = st;t = ed;
bfs();
memcpy (last, head, sizeof (head) );
while (d[s] < num) flow += dfs (s, INFLL);
return flow;
}
}Maxflow; int MaxFlow_check(int mid) { //建图，跑最大流
Maxflow.init(); //初始化
for (int i = ; i <= k ; i++) {
Maxflow.add(, i, m); //源点与机器相连，容量为m
for (int j = k + ; j <= k + c ; j++ )
if (mp[i][j] <= mid) Maxflow.add(i, j, ); //机器与牛相连,容量为1
}
for (int i = k + ; i <= k + c ; i++)
Maxflow.add(i, k + c + , ); //牛与汇点相连，容量为1
if ((int)(Maxflow.solve( , k + c + , k + c + )) == c) return ;
return ;
}
void Floyed(int n){
rep(k,,n) rep(i,,n) rep(j,,n){
mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
maxdist=max(maxdist,mp[i][j]); //找到最大的mp[i][j]，为寻找二分的上界
}
}
int main() {
while(~scanf("%d%d%d", &k, &c, &m)) {
for (int i = ; i <= k + c ; i++)
for (int j = ; j <= k + c ; j++) {
scanf("%d", &mp[i][j]);
if (i != j && !mp[i][j]) mp[i][j] = INF; //将0置为不可达
}
maxdist=-INF;Floyed(k+c);
int l = , r = maxdist ,ans = ;
while(l <= r) {
int mid = (l + r) >> ;
if (MaxFlow_check(mid))ans = mid,r = mid - ;
else l = mid + ;
}
printf("%d\n", ans);
}
return ;
}
2018-11-24