题意:
k台挤奶机,编号为1-k,c只奶牛,编号为k+1-k+c,一台机器可以工作m只奶牛,然后给出奶牛,挤奶机互相之间的距离,奶牛要去挤奶机那挤奶,问走最远的奶牛需要走的最小距离。
题解:
二分答案+floyed+网络流。
先用floyd预处理出任意两点之间的最短距离,然后二分答案mid,把图中距离大于mid的边全部舍弃,距离小于等于mid的边建流量为1的边,然后跑网络流进行检测,检测条件为最大流是否等于奶牛数量,
参考代码:
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 250;
const int inf = 1000000;
int k, c, m, n;
int mp[MAXN][MAXN];
struct EDGE
{
int v, nxt, w;
} edge[MAXN * MAXN];
int cnt = 0, fir[MAXN];
void addedge(int u, int v, int w)
{
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].nxt = fir[u];
fir[u] = cnt++;
}
void buildgraph(int x)
{
cnt = 0;
memset(fir, -1, sizeof(fir));
for (int i = 1; i <= k; i++)
{
addedge(i, n + 1, m);
addedge(n + 1, i, 0);
}
for (int i = k + 1; i <= n; i++)
{
addedge(0, i, 1);
addedge(i, 0, 0);
}
for (int i = 1; i <= k; i++)
for (int j = k + 1; j <= n; j++)
if (mp[i][j] <= x)
addedge(j, i, 1), addedge(i, j, 0);
}
int depth[MAXN], cur[MAXN], gap[MAXN];
void bfs(int st, int ed)
{
memset(gap, 0, sizeof(gap));
memset(depth, -1, sizeof(depth));
depth[ed] = 0, gap[0] = 1;
queue<int> que;
while (!que.empty())
que.pop();
que.push(ed);
while (!que.empty())
{
int u = que.front();
que.pop();
for (int i = fir[u]; i != -1; i = edge[i].nxt)
{
int v = edge[i].v;
if (depth[v] != -1)
continue;
que.push(v);
depth[v] = depth[u] + 1;
gap[depth[v]]++;
}
}
return;
}
int dfs(int u, int flow, int st, int ed)
{
if (u == ed)
return flow;
int tot = 0;
for (int &i = cur[u]; i != -1; i = edge[i].nxt)
{
int v = edge[i].v;
int w = edge[i].w;
if (w && depth[v] + 1 == depth[u])
{
int di = dfs(v, min(flow - tot, w), st, ed);
if (di)
{
edge[i].w -= di;
edge[i ^ 1].w += di;
tot += di;
}
if (tot == flow)
return flow;
}
}
gap[depth[u]]--;
if (gap[depth[u]] == 0)
depth[st] = n + 3;
depth[u]++;
gap[depth[u]]++;
return tot;
}
int ISAP(int st, int ed)
{
int sum = 0;
bfs(st, ed);
while (depth[st] < n + 2)
{
for (int i = 0; i <= n + 1; i++)
cur[i] = fir[i];
sum += dfs(st, inf, st, ed);
}
return sum;
}
int main()
{
while (scanf("%d%d%d", &k, &c, &m) != EOF)
{
n = k + c;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
scanf("%d", &mp[i][j]);
if (i != j && !mp[i][j])
mp[i][j] = inf;
}
for (int t = 1; t <= n; t++)
for (int u = 1; u <= n; u++)
for (int v = 1; v <= n; v++)
if (mp[u][v] > mp[u][t] + mp[t][v])
mp[u][v] = mp[u][t] + mp[t][v];
int l = 1, r = inf, ans = inf;
while (l < r)
{
int mid = (l + r) / 2;
buildgraph(mid);
int check = ISAP(0, n + 1);
if (check == c)
{
r = mid;
ans = mid;
}
else
l = mid + 1;
}
printf("%d\n", ans);
}
return 0;
}