题意：给你一张图，每个城市有一些人，有不超过10个城市有避难所，避难所有容量上限，问最快多久可以让所有人进入避难所？
思路：二分时间，对于每个时间跑一遍最大流，判断最大流是不是人数即可。我们还需要用二进制优化一下，对于每个二分的时间，我们需要预处理出某个城市可以到达哪些避难所，表示成状态。如果在当前时间下两个城市可以到达的避难所是一样的，我们就可以用一个状态表示，这样把点数限制在了1e3级别。
代码：
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#define LL long long
#define pLi pair<LL ,int>
#define pii pair<int, int>
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
using namespace __gnu_pbds;
const int maxn = 200100;
const int maxm = 501000;
typedef __gnu_pbds::priority_queue<pLi, greater<pLi>, pairing_heap_tag> Heap;
int heade[maxn],
Nexte[maxm], vere[maxm], edgee[maxm], tote;
LL dis[10][maxn];
pair<int, int> b[20];
int n, k;
int a[maxn];
LL re[maxn * 10];
void adde(int x, int y, int z) {
vere[++tote] = y;
edgee[tote] = z;
Nexte[tote] = heade[x];
heade[x] = tote;
}
Heap q;
int s, t;
void dijkstra(int s, int flag) {
memset(dis[flag], 0x3f, sizeof(dis[flag]));
Heap::point_iterator id[maxn];
dis[flag][s] = 0;
id[s] = q.push(make_pair(dis[flag][s], s));
while(!q.empty()) {
int x = q.top().second;
q.pop();
for (int i = heade[x]; i; i = Nexte[i]) {
int y = vere[i], z = edgee[i];
if(dis[flag][y] > dis[flag][x] + z) {
dis[flag][y] = dis[flag][x] + z;
if(id[y] != 0) q.modify(id[y], make_pair(dis[flag][y], y));
else id[y] = q.push(make_pair(dis[flag][y], y));
}
}
}
}
int head[maxn], Next[maxn * 25], ver[maxn * 25], tot;
LL edge[maxn * 25];
int deep[maxn];
void add(int x, int y, LL z) {
ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
ver[++tot] = x, edge[tot] = 0, Next[tot] = head[y], head[y] = tot;
}
queue<int> Q;
bool bfs(LL limit) {
memset(deep, 0, sizeof(deep));
while(Q.size())Q.pop();
Q.push(s); deep[s] = 1;
while(Q.size()) {
int x = Q.front();Q.pop();
for (int i = head[x]; i; i = Next[i]) {
if(edge[i] && !deep[ver[i]]) {
Q.push(ver[i]);
deep[ver[i]] = deep[x] + 1;
if(ver[i] == t) return 1;
}
}
}
return 0;
}
LL dinic(int x, LL flow) {
if(x == t) return flow;
LL rest = flow, k;
for (int i = head[x]; i && rest; i = Next[i]) {
if(edge[i] && deep[ver[i]] == deep[x] + 1) {
k = dinic(ver[i], min(rest, edge[i]));
if(!k) deep[ver[i]] = 0;
edge[i] -= k;
edge[i ^ 1] += k;
rest -= k;
}
}
return flow - rest;
}
LL solve(int now) {
tot = 1;
LL maxflow = 0;
// memset(head, 0, sizeof(head));
memset(head, 0, sizeof(int) * (n + 1));
for (int i = 0; i < k; i++)
head[b[i].first + n] = 0;
head[t] = 0;
for (int i = 1; i <= n; i++) {
if(a[i])
add(s, i, a[i]);
}
LL tmp;
for (int i = 1; i <= n; i++) {
tmp = 0;
if(a[i] == 0) continue;
for (int j = 0; j < k; j++) {
if(dis[j][i] >= re[now]) continue;
tmp += b[j].second;
add(i, b[j].first + n, INF);
}
if(tmp < a[i]) {
return 0;
}
}
for (int i = 0; i < k; i++)
add(b[i].first + n, t, b[i].second);
LL flow;
while(bfs(re[now])) {
while(flow = dinic(s, INF)) maxflow += flow;
}
return maxflow;
}
int main() {
LL cnt = 0;
s = 0, t = 2 * n + 20;
int m, x, y, z;
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
cnt += a[i];
}
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &x, &y, &z);
adde(x, y, z);
adde(y, x, z);
}
for (int i = 0; i < k; i++) {
scanf("%d%d", &b[i].first, &b[i].second);
dijkstra(b[i].first, i);
}
for (int i = 0; i < k; i++)
for (int j = 1; j <= n; j++) {
re[++tot] = dis[i][j];
}
sort(re + 1, re + 1 + tot);
int sz = unique(re + 1, re + 1 + tot) - (re + 1);
int l = 1, r = sz + 1;
re[sz + 1] = INF;
while(l < r) {
int mid = (l + r) >> 1;
if(solve(mid) == cnt) r = mid;
else l = mid + 1;
}
printf("%lld
", re[l - 1]);
}