网络流复习计划第二题 传送门

题意:
一个不负责任的地主有很多奶牛,他让奶牛们自己去产奶机器那里产奶,给你路径矩阵,产奶机器最多同时的奶牛是给定的,要你使走得最远的奶牛距离最短。

思路:
这题建边应该是我到现在写得比较妙的建图了。先是用flyod求出任意两个点的最短距离。(其实我们最主要想求的是每头奶牛与每台机器的最短距离)。然后我们二分这个距离区间,如下建边

  1. 对于每头奶牛对于每台机器最短距离小于等于我们的二分值limit ,则建边,流量为 1 。
  2. 建立超级源点,使得超级源点到每头牛的流量为 1 。
  3. 建立超级汇点,使得每台机器到超级汇点的流量为 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;
}