【题意】：有F块土地，每块土地都有一个牛棚，已知通过每两块土地之间的时间、每块土地的当前牛数和牛棚可以容纳牛的最大数目。问，在下雨的时候，至少需要多长时间使得每只牛都可以躲进牛棚。
【题解】：首先用floyd预处理通过每两块土地之间的最短时间。稍微分析一下可知：决定最终时间的肯定是需要通过的路中最长的那个时间。然后题目要求最小的时间，这显然是一个最大值最小化的问题。分析到这里的话，就很容易想到二分枚举答案了。具体做法：把每个牛棚i拆点成 i 和 i'；源点s向i连边，容量为牛棚i的当前牛数；i' 向汇点t连边，容量为牛棚i的最大容纳数量。二分时间mid，如果mid >= maz[i][j] 的话（maz[i][j]为通过牛棚i和牛棚j的最短时间），连边 i -> j’ 和 j -> i' ,容量均为inf。最后判断最大流是否等于所有牛的数目即可。该题需要用到long long。
【代码】：
1 #include "iostream"
2 #include "algorithm"
3 using namespace std;
4 #define maxn 505
5 #define maxm 1000010
6 const int INF = 1 << 29;
7 typedef __int64 LL;
8
9 struct Edge {
10 int u, v, cap, flow, next;
11 }et[maxm];
12
13 struct field {
14 int cow, cap;
15 }field[maxn];
16
17 int eh[maxn], tot, tot1, dist[maxn], pre[maxn], cur[maxn], a[maxn], gap[maxn];
18 LL maz[maxn][maxn], time[maxn*maxn];
19 int s, t, n, m, cow;
20
21 void init() {
22 tot = 0;
23 memset(eh, -1, sizeof(eh));
24 }
25
26 void add(int u, int v, int cap, int flow) {
27 Edge E = {u, v, cap, flow, eh[u]};
28 et[tot] = E;
29 eh[u] = tot++;
30 }
31
32 void addedge(int u, int v, int cap) {
33 add(u, v, cap, 0), add(v, u, 0, 0);
34 }
35
36 void floyd() {
37 for(int k = 1 ; k <= n ; k ++ )
38 for(int i = 1 ; i <= n ; i ++ )
39 for(int j = 1 ; j <= n ; j ++ )
40 if(maz[i][k] && maz[k][j]) {
41 if(maz[i][j] == 0) maz[i][j] = maz[i][k] + maz[k][j];
42 else maz[i][j] = min(maz[i][j], maz[i][k] + maz[k][j]);
43 }
44 tot1 = 0;
45 for(int i = 1 ; i <= n ; i ++ )
46 for(int j = i + 1 ; j <= n ; j ++ )
47 if(maz[i][j]) time[tot1++] = maz[i][j];
48 sort(time, time + tot1);
49 }
50
51 void build(LL limit) {
52 int i, j;
53 for(i = 1; i <= n; i++) {
54 addedge(i, i + n, INF);
55 if(field[i].cow) addedge(s, i, field[i].cow);
56 if(field[i].cap) addedge(i + n, t, field[i].cap);
57 }
58 for(i = 1 ; i <= n ; i++)
59 for(j = i + 1 ; j <= n ; j++)
60 if(maz[i][j] && maz[i][j] <= limit)
61 addedge(i, j + n, INF), addedge(j, i + n, INF);
62 }
63
64 int isap(int s, int t, int n) {
65 int u, v, now;
66 memset(dist, 0, sizeof(dist));
67 memset(a, 0, sizeof(a));
68 for(u = 0; u <= n; u++) cur[u] = eh[u];
69 int maxflow = 0;
70 u = s, a[s] = INF, gap[0] = n;
71 while(dist[s] < n) {
72 for(now = cur[u]; now != -1; now = et[now].next)
73 if(et[now].cap - et[now].flow && dist[u] == dist[v = et[now].v] + 1)
74 break;
75 if(now != -1) {
76 cur[u] = pre[v] = now;
77 a[v] = min(a[u], et[now].cap - et[now].flow);
78 u = v;
79 if(u == t) {
80 for(; u != s; u = et[pre[u]].u) {
81 et[pre[u]].flow += a[t];
82 et[pre[u]^1].flow -= a[t];
83 }
84 maxflow += a[t], a[s] = INF;
85 }
86 } else {
87 if(--gap[dist[u]] == 0) break;
88 dist[u] = n;
89 cur[u] = eh[u];
90 for(now = eh[u]; now != -1; now = et[now].next)
91 if(et[now].cap - et[now].flow && dist[u] > dist[et[now].v] + 1)
92 dist[u] = dist[et[now].v] + 1;
93 gap[dist[u]]++;
94 if(u != s) u = et[pre[u]].u;
95 }
96 }
97 return maxflow;
98 }
99
100
101 LL solve() {
102 LL res = -1;
103 int l = 0, r = tot1 - 1;
104 while(l <= r) {
105 int mid = (l + r) >> 1;
106 init();
107 build(time[mid]);
108 if(isap(s, t, t - s + 1) == cow) res = time[mid], r = mid -1;
109 else l = mid + 1;
110 }
111 return res;
112 }
113
114 int main() {
115 int u, v, i;
116 LL w;
117 while(~scanf("%d%d", &n, &m)) {
118 for(cow = 0, i = 1; i <= n; i++) {
119 scanf("%d%d", &field[i].cow, &field[i].cap);
120 cow += field[i].cow;
121 fill(maz[i], maz[i] + n + 1, 0);
122 }
123 for(i = 1; i <= m; i++) {
124 scanf("%d%d%I64d", &u, &v, &w);
125 if(maz[u][v]) w = min(w, maz[u][v]);
126 maz[u][v] = maz[v][u] = w;
127 }
128 s = 0, t = 2 * n + 1;
129 floyd();
130 printf("%I64d\n", solve());
131 }
132 return 0;
133 }