又是一些细节问题……
如果以我现在的水平去现场赛写网络流的题目,就算我会建图,我觉得还是挺悬的。

这里提前简单说一下dinic算法的最低上限的情况。
dinic的最高上限是 O ( ( V^2 E ) ) ,这是谁都知道的,然而对于一些特殊的图还有一些更低的上限。

在具有单位容量的网络中,Dinic算法可以在更短的时间内输出结果。每条阻塞流可以在 O ( E ) 的时间内构建,并且阶段的数量不超过 O( ( \sqrt E ) )或 O ( ( \sqrt[3] { V ^ 2 } ) )。此时算法的复杂度为 O ( ( min { ( \sqrt E , \sqrt[3] { V ^ 2 } ) } ) E )。
在二分图匹配问题的网络中,阶段的数量不超过 O ( ( \sqrt V ) ),算法的时间复杂度不超过 O ( ( \sqrt V E ) )。这种算法又被叫做Hopcroft-Karp算法。更普遍的情况是,这种复杂度对unit网络 — 网络中的顶点要么与源点相连,要么与汇点相连,要么是一个顶点的单一外向边,并且所有的容量限制都是整数。 —— 节选自 WIKI

简单说对于二分图,其上限为 不超过 O ( ( \sqrt V E ) ) 。

题意:
n个牛棚里面,各自有多头牛和空位,空为供给牛躲避。在牛棚之间总共有m条路并给定其长度。问让每头牛都有地方躲避最少需要多少时间。

思路:
floyd+二分+dinic
对于距离进行二分,距离最高 (10^{12} ) 大约是 (2^ {40} ) 。单次dinic 为 (\sqrt {200} ) × 1500 复杂度完全足够!
然而我在不知道对于二分图的复杂度居然如此之低,我根本不敢去想到对这么大的范围进行二分。
不不不,我的确想到了,但是被我一下子就否定了。

注: 注意数据范围

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 long long inf = 0x3f3f3f3f3f3f3f3f;

int n, m, idx, st, en;
int dis[maxn][maxn];
int level[maxn], cur[maxn], que[maxn * maxn];
int head[maxn];
long long mat[maxn / 2][maxn / 2];
int cow[maxn], cap[maxn];

struct node {
    long long flow;
    int to;
    int nxt;
} edges[100005];

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

    edges[idx].to = u;
    edges[idx].flow = 0;
    edges[idx].nxt = head[v];
    head[v] = 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, long long 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 <= 2 * n; i++)
            cur[i] = head[i];
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

void createGraph(long long len)
{
    memset(head, -1, sizeof head);
    idx = 0;
    for (int i = 1; i <= n; i++) {
        addEdge(i, i + n, inf);
        addEdge(st, i, cow[i]);
        addEdge(i + n, en, cap[i]);
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (mat[i][j] <= len)
                addEdge(i, j + n, inf);
}

int main()
{
    int u, v;
    long long ans, len;
    while (scanf("%d %d", &n, &m) != EOF) {
        memset(mat, 0x3f, sizeof mat);
        long long le = 0, ri = 0, mid, sum = 0;
        ans = -1, st = 0, en = n + n + 1;
        for (int i = 1; i <= n; i++) {
            scanf("%d %d", &cow[i], &cap[i]);
            sum += cow[i];
        }
        for (int i = 0; i < m; i++) {
            scanf("%d %d %lld", &u, &v, &len);
            mat[u][v] = mat[v][u] = min(mat[u][v], len);
        }
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                if (mat[i][j] != inf)
                    ri = max(ri, mat[i][j]);
            }
        while (le <= ri) {
            mid = (le + ri) >> 1;
            createGraph(mid);
            if (dinic() >= sum)
                ans = mid, ri = mid - 1;
            else
                le = mid + 1;
        }
        printf("%lld\n", ans);
    }
    return 0;
}