题目链接
题意
有(n)个牛棚，每个牛棚初始有(a_i)头牛，最后能容纳(b_i)头牛。有(m)条道路，边权为走这段路所需花费的时间。问最少需要多少时间能让所有的牛都有牛棚可待？
思路
二分
因为问题具有单调性，因此考虑二分时间，(check)是否满足条件。
满足条件指什么呢？
是指所有的牛都有牛棚可待。
是指所有的牛都顺利地从某一个牛棚移动到了另一个合法的牛棚（或者不移动），而这个移动是在限定的时间范围内的。
建图
首先拆点，将牛棚拆成 初始牛棚 与 终态牛棚。
-
在 源点 到 初始牛棚 之间连边，权值为初始时该牛棚内牛的个数。
-
在 终态牛棚 到 汇点 之间连边，权值为该牛棚最终可容纳的牛的个数。
-
在 初始牛棚 到 终态牛棚 之间连边：
((u_i,v_j),(v_i,u_j))：当且仅当移动的时间(d(i,j))小于当前(check)的值时，才可以连这条边；
((u_i,u_i))：因为无需花费时间，所以永远可以连上。
这两类边的权值都是(inf)，因为只要在限定的时间范围内，任意多的牛都可以从上面通过。
如果最大流对于源点而言是满流，则(check)成功
总括
综上所述，本题即最短路+二分+最大流
Code
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#define inf1 0x3f3f3f3f3f3f3f3f
#define inf2 0x3f3f3f3f
#define maxn 1010
#define maxm 200010
using namespace std;
typedef long long LL;
LL a[maxn][maxn], mx, d;
struct Edge { int to, ne, c; }edge[maxm];
int dep[maxn], ne[maxn], tmp[maxn], n,m, tot, s,t,num, x[maxn], y[maxn];
void add(int u, int v, int c) {
edge[tot] = {v, ne[u], c};
ne[u] = tot++;
edge[tot] = {u, ne[v], 0};
ne[v] = tot++;
}
int bfs(int src) {
memset(dep, 0, sizeof dep);
dep[src] = 1;
queue<int> q;
while (!q.empty()) q.pop();
q.push(src);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = ne[u]; ~i; i = edge[i].ne) {
int v = edge[i].to;
if (edge[i].c > 0 && !dep[v]) dep[v] = dep[u] + 1, q.push(v);
}
}
return dep[t];
}
int dfs(int u, int flow) {
if (u == t) return flow;
int ret = 0;
for (int i = ne[u]; ~i; i = edge[i].ne) {
int v = edge[i].to;
if (edge[i].c > 0 && dep[v] == dep[u] + 1) {
int c = dfs(v, min(flow-ret, edge[i].c));
edge[i].c -= c;
edge[i^1].c += c;
ret += c;
if (ret == flow) break;
}
}
if (!flow) dep[u] = 0;
return ret;
}
void floyd() {
for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) a[i][j] = inf1;
for (int i = 1; i <= n; ++i) a[i][i] = 0;
while (m--) {
int u, v;
scanf("%d%d%lld", &u, &v, &d);
a[u][v] = a[v][u] = min(a[u][v], d);
}
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (k==i||k==j) continue;
a[i][j] = a[j][i] = a[i][k]+a[k][j] < a[i][j] ? a[i][k]+a[k][j] : a[i][j];
}
}
}
mx = 0;
for (int i = 1; i <= n; ++i) for (int j = i+1; j <= n; ++j) if (a[i][j] != inf1) mx = max(mx, a[i][j]);
}
bool check(LL lim) {
tot = 0; memset(ne, -1, sizeof ne);
for (int i = 1; i <= n; ++i) {
add(s, i, x[i]); add(n+i, t, y[i]);
add(i, n+i, inf2);
}
int cnt = tot;
for (int i = s; i <= t; ++i) tmp[i] = ne[i];
for (int i = 1; i <= n; ++i) {
for (int j = i+1; j <= n; ++j) {
if (a[i][j] <= lim) add(i, n+j, inf2), add(j, n+i, inf2);
}
}
int ans=0, ret=0;
while (bfs(s)) {
while (ret = dfs(s, inf2)) ans += ret;
}
return ans == num;
}
int main() {
scanf("%d%d", &n, &m);
s = 0, t = n<<1|1, num = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &x[i], &y[i]);
num += x[i];
}
floyd();
LL l = 0, r = mx;
while (r > l) {
LL mid = l+r>>1;
if (check(mid)) r = mid;
else l = mid+1;
}
if (check(l)) printf("%lld
", l);
else puts("-1");
return 0;
}