题目描述：

f个地区。已知各个地区之间的行走时间。

每个地区i有两个属性：

这个地区当前牛的个数，下雨的时候这个地区实际能够容纳牛的个数。

问至少需要多少时间，使所有的牛在下雨的时候都能够被容纳。

解题报告：

最大流，二分，拆点。

f个地区，每个地区i拆成i和i + f

源点s连接1~f，容量是第一个属性。

f+1~2f 连接t，容量是第二个属性。

二分至少需要的时间mid。

如果a地区到b地区的时间小于等于mid。

连接a到b+f。容量无穷大。

如果最大流等于牛的总数，mid值合法。

代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define Max 0x1fffffff
#define size 500
struct edge{int from, to, val, next;}e[140000];
int v[size], que[size], dis[size], cnt, cur[size];
void insert(int from, int to, int va)
{
    e[cnt].from = from, e[cnt].to = to; e[cnt].val = va;
    e[cnt].next = v[from];v[from] = cnt++;
    e[cnt].from = to, e[cnt].to = from; e[cnt].val = 0;
    e[cnt].next = v[to];v[to] = cnt++;
}
bool bfs(int n, int s, int t)
{
    int head, tail, id;
    head = tail = 0; que[tail++] = s;
    memset(dis, -1, sizeof(int) * n);dis[s] = 0;
    while(head < tail) // bfs,得到顶点i的距s的最短距离dis[i]
        for(id = v[que[head++]]; id != -1; id = e[id].next)
            if (e[id].val > 0 && dis[e[id].to] == -1)
            {
                dis[e[id].to] = dis[e[id].from] + 1;
                que[tail++] = e[id].to;
                if (e[id].to == t) return true;
            }
    return false;
}

int Dinic(int n, int s, int t)
{
    int maxflow = 0, tmp, i;
    while(bfs(n, s, t))
    {
        int u = s, tail = 0;
        for(i = 0; i < n; i++) cur[i] = v[i];
        while(cur[s] != -1)
            if (u != t && cur[u] != -1 && e[cur[u]].val > 0 && dis[u] != -1 && dis[u] + 1 == dis[e[cur[u]].to])
            {que[tail++] = cur[u]; u = e[cur[u]].to;}
            else if (u == t)
            {
                for(tmp = Max, i = tail - 1; i >= 0; i--) tmp = min(tmp, e[que[i]].val);
                for(maxflow += tmp, i = tail - 1; i >= 0; i--)
                {
                    e[que[i]].val -= tmp;
                    e[que[i] ^ 1].val += tmp;
                    if (e[que[i]].val == 0) tail = i;
                }
                u = e[que[tail]].from;
            }
            else
            {
                while(tail > 0 && u != s && cur[u] == -1) u = e[que[--tail]].from;
                cur[u] = e[cur[u]].next;
            }
    }
    return maxflow;
}
int f, p, ee[size][2], s, t, num, jeonum;
long long ans, g[size][size];
struct Jeo
{
    int from, to;
    long long va;
}jeo[201 * 201];
bool cmp(Jeo a, Jeo b)
{
    return a.va < b.va;
}
void jeogia(long long mmax)
{
    long long l = 0, r = mmax + 1000;
    s = 0, t = (f << 1) + 1; ans = -1;
    while(l <= r)
    {
        long long mid = (l + r) >> 1LL;
        memset(v, -1, sizeof(v)); cnt = 0;
        for(int i = 1; i <= f; i++)
            insert(s, i, ee[i][0]),insert(i + f, t, ee[i][1]);
        for(int i = 0; i < jeonum; i++)
            if (jeo[i].va > mid) break;
            else insert(jeo[i].from, jeo[i].to, Max);
        int tmp = Dinic(t + 1, s, t);
        if (tmp >= num)
        {
            if (ans == -1 || mid < ans) ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
}
int main()
{
    while(scanf("%d%d", &f, &p) != EOF)
    {
        for(int i = 1; i <= f; i++)
            for(int j = 1; j <= f; j++)
                g[i][j] = (i == j ? 0 : -1);
        num = 0; long long mmax = -1;
        for(int i = 1; i <= f; i++)
        {
            scanf("%d%d", &ee[i][0], &ee[i][1]);
            num += ee[i][0];
        }
        for(int i = 0; i < p; i++)
        {
            int a, b; long long c;
            scanf("%d%d%I64d", &a, &b, &c);
            if (g[a][b] == -1 || c < g[a][b]) g[b][a] = g[a][b] = c;
        }
        for(int k = 1; k <= f; k++)
            for(int i = 1; i <= f; i++)
            {
                if (g[i][k] == -1) continue;
                for(int j = 1; j <= f; j++)
                    if (g[k][j] != -1 && (g[i][j] == -1 || g[i][k] + g[k][j] < g[i][j]))
                    {
                        g[i][j] = g[i][k] + g[k][j];
                        if (g[i][j] > mmax) mmax = g[i][j];
                    }
            }
        jeonum = 0;
        for(int i = 1; i <= f; i++)
            for(int j = 1; j <= f; j++)
            {
                if (g[i][j] != -1)
                {
                    jeo[jeonum].from = i;
                    jeo[jeonum].to = j + f;
                    jeo[jeonum++].va = g[i][j];
                }
            }
        sort(jeo, jeo + jeonum, cmp);
        jeogia(mmax);
        printf("%I64d\n", ans);

    }
    return 0;
}