最大流

SPOJ 287 Smart Network Administrator

Posted on

坑哭了……
先是一个小地方初始化错误,tle了5发,看到下面说数据很多,还尝试开了输入挂……

然后数组开小,WA了n发

题意:
村通网系列。一个村子只有1号家庭有网络,现在有k家用户想要通网,为了网络质量,在一条街道上的每条网络都必须是不同的网线。问最少需要多少掉网线。(差不多就是这样的,颜色什么的就别管了……)

思路:
这道题我看完第一个想法就是二分,但是因为dinic的复杂度问题不是很敢写。搜了一下题解,居然真的是二分……众所周知dinic的复杂度上限为 O(n^2 * m) 如果是稠密图,最高可达 O(n^4) 二分最多9次,除开重新建图,数据最多500组,n最多500,也就是 500^5 ……

然而结果是 0.69 ,我也不知道是什么单位,在spoj刷题是几百年前了…… ,应该是 s 吧。

AC code

#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 n, m, k, st, en, idx;
int dis[maxn][maxn];
int level[maxn], cur[maxn], que[maxn * maxn];
int customer[maxn], head[maxn], from[maxn], to[maxn];

struct node {
    int to;
    int nxt;
    int flow;
} edges[2 * maxn * maxn];

inline void addEdge(int u, int v, int flow)
{
    edges[idx].to = v;
    edges[idx].flow = flow;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

inline bool scan_d(int& num)
{
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF)
        return false;
    while (in != '-' && (in < '0' || in > '9'))
        in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else
        num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') {
        num *= 10, num += in - '0';
    }
    if (IsN)
        num = -num;
    return true;
}

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 id = head[u]; ~id; id = edges[id].nxt) {
            int v = edges[id].to;
            if (edges[id].flow && level[v] == -1) {
                level[v] = level[u] + 1;
                que[r++] = v;
            }
        }
    }
    return level[en] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == en)
        return low;
    for (int& id = cur[u]; ~id; id = edges[id].nxt) {
        int v = edges[id].to;
        if (edges[id].flow && level[v] == level[u] + 1
            && (cflow = dfs(v, min(low, edges[id].flow)))) {
            edges[id].flow -= cflow;
            edges[id ^ 1].flow += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic()
{
    int ans = 0, cflow;
    while (bfs()) {
        for (int i = 0; i <= 2 * n; i++)
            cur[i] = head[i];
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

inline void resetGraph(int len)
{
    memset(head, -1, sizeof head);
    idx = 0;
    for (int i = 0; i < m; i++) {
        addEdge(from[i], to[i], len);
        addEdge(to[i], from[i], len);
    }
    for (int i = 0; i < k; i++) {
        addEdge(customer[i], 0, 1);
        addEdge(0, customer[i], 0);
    }
}

int main()
{
    int T;
    scan_d(T);
    while (T--) {
        scan_d(n);
        scan_d(m);
        scan_d(k);
        st = 1, en = 0;
        for (int i = 0; i < k; i++)
            scan_d(customer[i]);
        for (int i = 0; i < m; i++) {
            scan_d(from[i]);
            scan_d(to[i]);
        }
        int l = 0, r = k, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            resetGraph(mid);
            if (dinic() >= k)
                r = mid - 1;
            else
                l = mid + 1;
        }
        printf("%d\n", r + 1);
    }
    return 0;
}

最大流

ZOJ 2760 How Many Shortest Path

Posted on

暑假集训第一天,早上看了一下支配树,结果表示完全不会,看不懂……不得不回老本写起了网络流

题意:
给你一个距离矩阵,问你完全不重叠的最短路数目。

思路:
完全不重叠,意为每条边只能走一次,我以网络流建模,对于每条在最短路径内的边的流量设置为1,跑出来的结果即题意所求。这个很自然想得到吧
关键就在于如何判断一条边是否属于最短路径。
这里给出一种比较好的方法,对于一条边 ( u , v ) ,如果 min ( st , u ) + ( u,v ) + min ( v , en ) 等于最短路径长度,那么这条边就属于最短路径 这也是很显然的

注: 如果起点与终点相同,则直接输出inf ,本人英语不好,看了一下题意我还意淫成了 如果存在( st , en ) 就输出inf。
结果我tle了4发……
因为一直wa我看了一下其他题解,居然有人以自环>=0为理由A不了……我感觉很奇怪。如果自环权值非负,那么正权值自环必定不在最短路径中,而零自环加不加都没有任何影响。

其他的就是代码美丑的问题了。

AC code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
using namespace std;
const int maxn = 105;
const int inf = 0x3f3f3f3f;

int n, idx, st, en;
int dis[maxn][maxn];
int level[maxn], cur[maxn], que[maxn * maxn];
int head[maxn];
int mat[maxn][maxn];
int diss[maxn], dist[maxn], cpmat[maxn][maxn];

struct node {
    int flow;
    int to;
    int nxt;
} edges[4 * maxn * maxn];

void addEdge(int u, int v, int f)
{
    edges[idx].to = v;
    edges[idx].flow = f;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

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 id = head[u]; ~id; id = edges[id].nxt) {
            int v = edges[id].to;
            if (edges[id].flow && level[v] == -1) {
                level[v] = level[u] + 1;
                que[r++] = v;
            }
        }
    }
    return level[en] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == en)
        return low;
    for (int& id = cur[u]; ~id; id = edges[id].nxt) {
        int v = edges[id].to;
        if (edges[id].flow > 0 && level[v] == level[u] + 1
            && (cflow = dfs(v, min(low, edges[id].flow)))) {
            edges[id].flow -= cflow;
            edges[id ^ 1].flow += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic()
{
    int ans = 0, cflow;
    while (bfs()) {
        for (int i = 0; i <= n; i++)
            cur[i] = head[i];
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

void spfa(int s, int* dis, int sp[maxn][maxn])
{
    bool vis[maxn];
    int que[maxn];
    memset(vis, false, sizeof vis);
    for (int i = 0; i <= n; i++)
        dis[i] = inf;
    dis[s] = 0;
    vis[s] = true;
    int l = 0, r = 1;
    que[0] = s;
    while (l < r) {
        int u = que[l++];
        vis[u] = 0;
        for (int v = 1; v <= n; v++) {
            if (dis[v] > dis[u] + sp[u][v]) {
                dis[v] = dis[u] + sp[u][v];
                if (!vis[v]) {
                    vis[v] = 1;
                    que[r++] = v;
                }
            }
        }
    }
}

bool createGraph()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cpmat[i][j] = mat[j][i];
    memset(head, -1, sizeof head);
    idx = 0;
    st++, en++;
    spfa(st, diss, mat);
    spfa(en, dist, cpmat);
    //printf("dist --> %d %d %d %d\n", dist[1], dist[2], dist[3], dist[4]);
    int min_len = diss[en];
    if (min_len == inf)
        return false;
    for (int u = 1; u <= n; u++)
        for (int v = 1; v <= n; v++) {
            if (diss[u] + mat[u][v] + dist[v] == min_len) {
                //printf("%d %d %d %d %d\n", diss[u], mat[u][v], dist[v], u, v);
                addEdge(u, v, 1);
                addEdge(v, u, 0);
            }
        }
    return true;
}

int main()
{
    int len;
    while (scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                scanf("%d", &len);
                mat[i][j] = len < 0 ? inf : len;
            }
        scanf("%d %d", &st, &en);
        if (st == en) {
            puts("inf");
            continue;
        }
        if (createGraph())
            printf("%d\n", dinic());
        else
            puts("0");
    }
    return 0;
}

最大流

POJ 1149 PIGS

Posted on

本来在学校新搞的vj上挂了一套网络流的题打算大刷特刷,突然发现还有两天就考毛概了……然而我又一点也没看……不得不先把它放下。

是昨天考完开始看这题的……想了大概3个小时,否定了很多想法,然后就没去想了……因为据说是比较经典的构图题,本来还想自己想出来的,结果今天还是没办法去看了题解,顺便发现了个好东西。
网络流建模汇总

不得不说这道题的构图思路真是巧妙,而且我自己的想法与题解的想法真的已经十分接近了……
十分建议在看题解之前好好思考构图。

题意:
有n个人买猪,总共有m个猪圈,每个人只能去特定的猪圈买猪,按照给定顺序买,在每次购买之后管理员都可以自由调整这位顾客所能购买的猪圈里的剩下的猪,以便使得卖出的猪最多。问最多能卖多少。

思路:
先放可行思路
+ 每个顾客分别用一个结点来表示。
+ 对于每个猪圈的第一个顾客,从源点向他连一条边,容量就是该猪圈里的猪的初始数量。如果从源点到一名顾客有多条边,则可以把它们合并成一条,容量相加。
+ 对于每个猪圈,假设有 n 个顾客打开过它,则对所有整数 i∈[1, n),从该猪圈的第 i 个顾客向第 i + 1 个顾客连一条边,容量为 inf 。
+ 从各个顾客到汇点各有一条边,容量是各个顾客能买的数量上限。

如果是思考良久的你理解了这个构图法一定会拍手称快,我这里简单解释一下
构图最巧妙的地方在于顾客之间的流量,对于两个顾客,如果他们的起始可买猪圈集合有交集,那么他们最终实际可购买集合就是两个集合的并集,因此流量设为 inf 。
至于猪圈的省略缩点,也可以算是巧妙,但一般都想得到,就不解释了。

详细的构图思路见上述文档。

而我的不可行思路则是源点与汇点反过来,以人的购买需求为流量,想要在猪之间构建边,一直得不到正解……

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>

using namespace std;
const int maxn = 310;
const int inf = 0x3f3f3f3f;

int n, m, st, en;
int dis[maxn][maxn];
int flow[maxn][maxn];
int level[maxn], cur[maxn], que[maxn * maxn];
vector<int> vec[maxn * 10];
int val[maxn];

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 <= en; 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 <= en; 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()
{
    int ans = 0, cflow;
    while (bfs()) {
        memset(cur, 0, sizeof cur);
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

int main()
{
    int f, num, pighouse;
    while (scanf("%d %d", &m, &n) != EOF) {
        st = 0, en = n + 1;
        memset(flow, 0, sizeof flow);
        for (int i = 1; i <= m; i++)
            scanf("%d", val + i);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &num);
            for (int j = 0; j < num; j++) {
                scanf("%d", &pighouse);
                vec[pighouse].push_back(i);
            }
            scanf("%d", &f);
            flow[i][en] = f;
        }
        for (int i = 1; i <= m; i++) {
            int pre = vec[i][0], sz = vec[i].size(), cur;
            flow[st][pre] += val[i];
            for (int j = 1; j < sz; j++) {
                cur = vec[i][j];
                flow[pre][cur] = inf;
                pre = cur;
            }
        }
        printf("%d\n", dinic());
    }
    return 0;
}
最大流

HDU 3572 Task Schedule

Posted on

网络流复习计划第四题,前几天在复习全国公认挂科率最高的数电,所以一直没做题。

扯一个,数电最后没复习好正打算放弃的时候被老友傻炮拉了一把。应该可以过。

题意:
给你很多任务,每个任务都需要一台机器花费给定的时间才能完成,并且限定了每个任务的完成时间区间( 比如说 [a,b] 在第a天开始,在第b天之前完成,包括b),一台机器一天只能执行一个任务,有多台机器。问你是否能全部完成任务。

思路:
先歪一个……一开始我看到这题想了一下是想贪心做的,结果在写的过程中就自己 否定--更改 了好几次,结果还是没写出来。
实际上这道题是网络流建图的一道经典题,我们让每一个任务作为流量源点,将每个流量源点与其任务时间区间的每个数建边,流量为1,表示你可以在这个区间内其中任意一天使用一台机器,而每台机器将其作为汇点汇入一个超级汇点即可。
他的数据范围最大都只有500,因为要新建流量源点,所以所有节点数量不超过1000。我觉得复杂度还可以啊,但是discuss里面一堆人都说卡时间,过不去……感觉很奇怪,我是1A的,263s,还没有特意去记录点数,懒得优化……

AC code

#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 n, m, st, en;
int dis[maxn][maxn];
int flow[maxn][maxn];
int level[maxn], cur[maxn], que[maxn * maxn];

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 <= 1001; 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 <= 1001; 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 = 1001;
    int ans = 0, cflow;
    while (bfs()) {
        memset(cur, 0, sizeof cur);
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

int main()
{
    int T, s, e, len;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d %d", &m, &n);
        memset(flow, 0, sizeof flow);
        int sum = 0;
        for (int i = 1; i <= m; i++) {
            scanf("%d %d %d", &len, &s, &e);
            sum += len;
            flow[0][500 + i] = len;
            for (int j = s; j <= e; j++)
                flow[500 + i][j] = 1;
        }
        for (int i = 1; i <= 500; i++)
            flow[i][1001] = n;
        printf("Case %d: %s\n\n", cas,dinic()==sum?"Yes":"No");
    }
    return 0;
}
BFS

UVa 11624 基础BFS

Posted on

白书训练指南上的第一道基础题,因为它在搜索中引入了超级源点,所以我自己试着做了一下,真的宛如发现新大陆一般,图论的建图技巧真的是在整个图论领域都十分适用啊。

因为UVa的尿性,写完去搜一下题解,居然有很多题解都是两次 bfs ……真是笑了

题意:
一个起火的迷宫,有很多起火的地点,给你初始位置,和起火地点,你的逃跑速度和火焰蔓延速度相等,问你能否跑出迷宫,若能,输出最短时间。

思路:
网上那些两遍bfs的应该是先一遍bfs处理出火焰蔓延到每一个格子的最短时间,在自己bfs时间加个时间大小判断的限制。
然而实际上,我们溶入超级源点的思路,然所有点一起开始跑,在同一个时间内,让所有火焰先跑,并加以标记,而人则把火焰和墙壁一起处理,避而不走。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

using namespace std;
const int maxn = 1010;

int row, col, st, en;
char mat[maxn][maxn];
bool vis[maxn][maxn];
int dx[] = { 0, -1, 0, 1 };
int dy[] = { -1, 0, 1, 0 };

struct node {
    int x, y;
    int time;
    bool is_fire;
    node() {}
    node(int _x, int _y, int _time, bool _fire)
        : x(_x)
        , y(_y)
        , time(_time)
        , is_fire(_fire)
    {
    }
} tmp;

queue<node> que;

int bfs()
{
    memset(vis, 0, sizeof vis);
    vis[st][en] = true;
    int x, y, time;
    bool is_fire;
    while (!que.empty()) {
        tmp = que.front();
        que.pop();
        x = tmp.x, y = tmp.y, time = tmp.time, is_fire = tmp.is_fire;
        if (!is_fire && (x == 0 || x == row - 1 || y == 0 || y == col - 1))
            return time + 1;
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 0 && xx < row && yy >= 0 && yy < col && !vis[xx][yy] && mat[xx][yy] != '#') {
                if (is_fire) {
                    mat[xx][yy] = 'F';
                    que.push(node(xx, yy, time + 1, true));
                } else if (mat[xx][yy] == 'F')
                    continue;
                else
                    que.push(node(xx, yy, time + 1, false));
                vis[xx][yy] = true;
            }
        }
    }
    return -1;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &row, &col);
        while (!que.empty())
            que.pop();
        for (int i = 0; i < row; i++)
            scanf("%s", mat[i]);
        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++) {
                if (mat[i][j] == 'F')
                    que.push(node(i, j, 0, true));
                else if (mat[i][j] == 'J')
                    st = i, en = j;
            }
        que.push(node(st, en, 0, false));
        int ans = bfs();
        if (ans == -1)
            puts("IMPOSSIBLE");
        else
            printf("%d\n", ans);
    }
    return 0;
}

最大流

POJ 2455 Secret Milking Machine

Posted on

网络流复习计划第三题 传送门
啊,这道题的建图完全是自己想的,虽然花的时间比较长,但是还是算是1A了(交了第一发忘记删了文件输入……),老实说,A的有点意外呀……

题意:
小气的农场主发现了个大宝贝并把他藏在了n点,他家在1点,总共n个点有若干条路,谨慎的农场主怕自己的宝贝被偷走,于是要从家里出发,结点不重复的走到大宝贝t次。问你在农场主所走的路径中最长的两点距离最短为多少。

思路:
当然还是二分啦!
先是建立距离图。再二分距离,再额外建图,若两点距离小于等于二分值 limit ,则建立双向建边,流量均为 1 。再跑一次dinic,如果总流量大于等于 t ,说明这个limit是满足条件的,我们再尝试缩小它,否则,增大它。

注意: 此题存在重边,存在重边的图,必须用邻接表存储。为什么来着,突然忘了,以后再补

//wordpress的markdown插件有个bug,代码太长的话头文件就显示不了,现在暂时分开……

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
using namespace std;
const int maxn = 210;
const int inf = 0x3f3f3f3f;

int n, m, c, idx, nidx, st, en;
int dis[maxn][maxn];
int level[maxn], cur[maxn], que[maxn * maxn];
int head[maxn], nhead[maxn];

struct node {
    int to;
    int flow;
    int nxt;
} edges[2 * maxn * maxn], nedges[2 * maxn * maxn];

void addEdge(int u, int v, int flow)
{
    edges[idx].to = v;
    edges[idx].nxt = head[u];
    edges[idx].flow = flow;
    head[u] = idx++;
}

inline void addNetEdge(int u, int v)
{
    nedges[nidx].to = v;
    nedges[nidx].nxt = nhead[u];
    nedges[nidx].flow = 1;
    nhead[u] = nidx++;

    nedges[nidx].to = u;
    nedges[nidx].nxt = nhead[v];
    nedges[nidx].flow = 1;
    nhead[v] = nidx++;
}

inline void createGragh(int limit)
{
    memset(nhead, -1, sizeof head);
    nidx = 0;
    for (int i = 1; i <= n; i++)
        for (int u = head[i]; ~u; u = edges[u].nxt) {
            if (edges[u].flow <= limit) {
                addNetEdge(i, edges[u].to);
            }
        }
}

bool bfs()
{
    memset(level, -1, sizeof level);
    que[0] = st;
    level[st] = 0;
    int l = 0, r = 1, u, v;
    while (l < r) {
        u = que[l++];
        for (int i = nhead[u]; ~i; i = nedges[i].nxt) {
            v = nedges[i].to;
            if (nedges[i].flow && level[v] == -1) {
                level[v] = level[u] + 1;
                que[r++] = v;
            }
        }
    }
    return level[en] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == en)
        return low;
    for (int& i = cur[u]; ~i; i = nedges[i].nxt) {
        int v = nedges[i].to;
        if (nedges[i].flow > 0 && level[v] == level[u] + 1
            && (cflow = dfs(v, min(low, nedges[i].flow)))) {
            nedges[i].flow -= cflow;
            nedges[i ^ 1].flow += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic()
{
    st = 1, en = n;
    int ans = 0, cflow;
    while (bfs()) {
        for (int i = 1; i <= n; i++)
            cur[i] = nhead[i];
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

void init()
{
    idx = 0;
    memset(head, -1, sizeof head);
}

int main()
{
    int u, v, w;
    while (scanf("%d %d %d", &n, &m, &c) != EOF) {
        init();
        int l = 0, r = 0, mid;
        while (m--) {
            scanf("%d %d %d", &u, &v, &w);
            addEdge(u, v, w);
            r = max(r, w);
        }
        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;
}
最大流

POJ 2112 Optimal Milking

Posted on

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

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

思路:
这题建边应该是我到现在写得比较妙的建图了。先是用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;
}