网络流复习计划第二题 传送门
题意：
一个不负责任的地主有很多奶牛，他让奶牛们自己去产奶机器那里产奶，给你路径矩阵，产奶机器最多同时的奶牛是给定的，要你使走得最远的奶牛距离最短。
思路：
这题建边应该是我到现在写得比较妙的建图了。先是用flyod求出任意两个点的最短距离。(其实我们最主要想求的是每头奶牛与每台机器的最短距离)。然后我们二分这个距离区间，如下建边
- 对于每头奶牛对于每台机器最短距离小于等于我们的二分值limit ,则建边，流量为 1 。
- 建立超级源点，使得超级源点到每头牛的流量为 1 。
- 建立超级汇点，使得每台机器到超级汇点的流量为 m。
每次二分跑一遍dinic，如果流量等于牛的数量，则可以缩短距离。
注： 这道题值得注意的坑点有
- 结点数已改，应该是在1000以上
- 距离矩阵距离为0应该改成inf
给我好好读题呀！！！ - k是机器数，c是奶牛数…… （我就一直wa在这里……
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
using namespace std;
const int maxn = 1010;
const int inf = 0x3f3f3f3f;
int k, c, m, mlen, st, en;
int dis[maxn][maxn];
int flow[maxn][maxn];
int level[maxn], cur[maxn], que[maxn * maxn];
inline void createGragh(int limit)
{
memset(flow, 0, sizeof flow);
for (int i = k + 1; i <= mlen; i++)
for (int j = 1; j <= k; j++)
flow[i][j] = dis[i][j] <= limit;
for (int i = 1; i <= k; i++)
flow[i][mlen + 1] = m;
for (int i = k + 1; i <= mlen; i++)
flow[0][i] = 1;
}
bool bfs()
{
memset(level, -1, sizeof level);
que[0] = st;
level[st] = 0;
int l = 0, r = 1, u;
while (l < r) {
u = que[l++];
for (int i = 0; i < mlen + 2; i++)
if (flow[u][i] && level[i] == -1) {
level[i] = level[u] + 1;
que[r++] = i;
}
}
return level[en] != -1;
}
int dfs(int u, int low)
{
int cflow;
if (u == en)
return low;
for (int& i = cur[u]; i < mlen + 2; i++) {
if (flow[u][i] > 0 && level[i] == level[u] + 1
&& (cflow = dfs(i, min(low, flow[u][i])))) {
flow[u][i] -= cflow;
flow[i][u] += cflow;
return cflow;
}
}
return 0;
}
int dinic()
{
st = 0, en = mlen + 1;
int ans = 0, cflow;
while (bfs()) {
memset(cur, 0, sizeof cur);
while ((cflow = dfs(st, inf)))
ans += cflow;
}
return ans;
}
int main()
{
while (scanf("%d %d %d", &k, &c, &m) != EOF) {
mlen = k + c;
int l = 0, r = 0, mid;
for (int i = 1; i <= mlen; i++) {
for (int j = 1; j <= mlen; j++) {
scanf("%d", &dis[i][j]);
if (dis[i][j] == 0)
dis[i][j] = inf;
}
}
for (int p = 1; p <= mlen; p++)
for (int i = 1; i <= mlen; i++)
for (int j = 1; j <= mlen; j++)
if (dis[i][j] > dis[i][p] + dis[p][j])
dis[i][j] = dis[i][p] + dis[p][j];
for (int i = 1; i <= mlen; i++)
for (int j = 1; j <= mlen; j++)
r = max(r, dis[i][j]);
while (l <= r) {
mid = (l + r) >> 1;
createGragh(mid);
if (dinic() == c)
r = mid - 1;
else
l = mid + 1;
}
printf("%d\n", r + 1);
}
return 0;
}