又是一些细节问题……
如果以我现在的水平去现场赛写网络流的题目，就算我会建图，我觉得还是挺悬的。
这里提前简单说一下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;
}