题目地址：POJ：2391 — Ombrophobic Bovines、OpenJudge百练：OpenJudge – 2391:Ombrophobic Bovines

题目描述

FJ’s cows really hate getting wet so much that the mere thought of getting caught in the rain makes them shake in their hooves. They have decided to put a rain siren on the farm to let them know when rain is approaching. They intend to create a rain evacuation plan so that all the cows can get to shelter before the rain begins. Weather forecasting is not always correct, though. In order to minimize false alarms, they want to sound the siren as late as possible while still giving enough time for all the cows to get to some shelter.
The farm has F (1 <= F <= 200) fields on which the cows graze. A set of P (1 <= P <= 1500) paths connects them. The paths are wide, so that any number of cows can traverse a path in either direction.
Some of the farm’s fields have rain shelters under which the cows can shield themselves. These shelters are of limited size, so a single shelter might not be able to hold all the cows. Fields are small compared to the paths and require no time for cows to traverse.
Compute the minimum amount of time before rain starts that the siren must be sounded so that every cow can get to some shelter.
给定一张的无向图，每条边有长度。点i处有ai头牛，以及一个能容纳bi头牛的牛棚。牛可以沿边移动，每条边上可以同时有任意头牛经过。一头牛经过一条边所需时间即为道路长度。
给出一个将牛分配到牛棚的方案，并最小化所需移动时间T。

输入输出格式

输入格式：
* Line 1: Two space-separated integers: F and P
* Lines 2..F+1: Two space-separated integers that describe a field. The first integer (range: 0..1000) is the number of cows in that field. The second integer (range: 0..1000) is the number of cows the shelter in that field can hold. Line i+1 describes field i.
* Lines F+2..F+P+1: Three space-separated integers that describe a path. The first and second integers (both range 1..F) tell the fields connected by the path. The third integer (range: 1..1,000,000,000) is how long any cow takes to traverse it.

输出格式：
* Line 1: The minimum amount of time required for all cows to get under a shelter, presuming they plan their routes optimally. If it not possible for the all the cows to get under a shelter, output “-1”.

输入输出样例

输入样例#1：

3 4
7 2
0 4
2 6
1 2 40
3 2 70
2 3 90
1 3 120

输出样例#1：

110

说明

OUTPUT DETAILS:
In 110 time units, two cows from field 1 can get under the shelter in that field, four cows from field 1 can get under the shelter in field 2, and one cow can get to field 3 and join the cows from that field under the shelter in field 3. Although there are other plans that will get all the cows under a shelter, none will do it in fewer than 110 time units.

题解

我们不好直接求这个移动时间，但是如果固定了一个时间，我们可以通过构图最大流来判断是否可行。
如果说已知了时间，我们可以将每个位置拆点，分别代表牛和牛棚，分别向源汇连边，容量控制牛的数量或牛棚的容量。牛与牛棚之间的边由最长时间来决定。我们可以预先跑一遍Floyd，处理出最短路。如果最短路并未超过二分的时间，那么就可以加边。如果代表牛的点满流，则所有牛都可以分配进牛棚里，即满足条件。
注：下面的代码在POJ上TLE了，但是可以通过OpenJudge百练的评测以及官方数据的测试。官方数据下载

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>

#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXE = 400005, MAXV = 405;
const int INF = 1e9;

struct Edge {
    int to, cap, nxt;
} gra[MAXE << 1];
int head[MAXV], tot;

inline void reset() {
    memset(head, -1, sizeof(head)); tot = 0;
}

inline void addedge(int u, int v, int cap) {
    gra[tot] = Edge {v, cap, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, head[v]}; head[v] = tot++;
}

int n, m;

LL dis[MAXV][MAXV];

inline void floyd() {
    for(register int k = 1; k <= n; k++) {
        for(register int i = 1; i <= n; i++) {
            for(register int j = 1; j <= n; j++) {
                dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
}

int level[MAXV], cur[MAXV];
std::queue<int> que;

inline bool bfs(int s, int t) {
    memset(level, -1, sizeof(level));
    level[s] = 0;
    que.push(s);
    while(!que.empty()) {
        register int u = que.front(); que.pop();
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(level[v] == -1 && gra[i].cap > 0) {
                level[v] = level[u] + 1;
                que.push(v);
            }
        }
    }
    return level[t] != -1;
}

bool vis[MAXV];

inline int dfs(int u, int t, int left) {
    if(u == t || left == 0) return left;
    register int flow = 0; vis[u] = true;
    for(int &i = cur[u]; ~i; i = gra[i].nxt) {
        register int v = gra[i].to;
        if(gra[i].cap > 0 && !vis[v] && level[v] == level[u] + 1) {
            int d = dfs(v, t, std::min(left, gra[i].cap));
            if(d > 0) {
                flow += d; left -= d;
                gra[i].cap -= d; gra[i ^ 1].cap += d;
                if(left == 0) {
                    level[u] = -1;
                    return flow;
                }
            }
        }
    }
    return flow;
}

inline int dinic(int s, int t) {
    register int flow = 0;
    while(bfs(s, t)) {
        memcpy(cur, head, sizeof(head));
        memset(vis, 0, sizeof(vis));
        register int f;
        while(f = dfs(s, t, INF)) {
            flow += f;
        }
    }
    return flow;
}

int cnum[MAXV], snum[MAXV], csum;
int S, T;

// 1~n cow
// n+1~2n shelter

inline bool check(LL mid) {
    reset();
    for(register int i = 1; i <= n; i++) {
        addedge(S, i, cnum[i]);
        addedge(i + n, T, snum[i]);
        addedge(i, i + n, INF);
    }
    for(register int i = 1; i <= n; i++) {
        for(register int j = i + 1; j <= n; j++) {
            if(dis[i][j] <= mid) {
                addedge(i, j + n, INF);
                addedge(j, i + n, INF);
            }
        }
    }
    return dinic(S, T) >= csum;
}

int ut, vt;
LL wt;

int main() {
    n = readint(); m = readint(); S = 2 * n + 1; T = S + 1;
    for(register int i = 1; i <= n; i++) {
        cnum[i] = readint(); snum[i] = readint();
        csum += cnum[i];
    }
    memset(dis, 0x3f, sizeof(dis));
    for(register int i = 1; i <= m; i++) {
        ut = readint(); vt = readint(); wt = readint();
        dis[ut][vt] = dis[vt][ut] = std::min(dis[ut][vt], wt);
    }
    for(register int i = 1; i <= n; i++) {
        dis[i][i] = 0;
    }
    floyd();
    register LL l = 0, r = 1e16, mid;
    while(r - l > 1) {
        mid = (l + r) >> 1;
        if(check(mid)) r = mid; else l = mid;
    }
    if(r != 1e16) printf("%lld", r); else puts("-1");
    return 0;
}