POJ 2455：Secret Milking Machine（二分+最大流）

题意：给出n个点和m条无向路，每条路都有一个长度。从1点到n点要走t次两两互不重合的路。求出每条1->n的路中相邻两点最大值的最小值。

思路：题目就是要最小化最大值，因此可以二分枚举当前的最大长度，如果长度小于等于当前枚举的值的话，就可以给它容量，否则就设容量为0，然后跑一遍最大流判断是否流量大于等于t，根据情况更新图。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 using namespace std;
 5 #define N 410
 6 #define INF 0x3f3f3f3f
 7 struct Edge {
 8     int v, nxt, cap, w;
 9     Edge () {}
10     Edge (int v, int nxt, int cap, int w) : v(v), nxt(nxt), cap(cap), w(w) {}
11 } edge[N*N];
12 int head[N], tot, dis[N], cur[N], pre[N], gap[N], n, m, t;
13 
14 void Add(int u, int v, int cap, int w) {
15     edge[tot] = Edge(v, head[u], cap, w); head[u] = tot++;
16     edge[tot] = Edge(u, head[v], 0, w); head[v] = tot++;
17 }
18 
19 int BFS(int S, int T) {
20     queue<int> que; que.push(T);
21     memset(dis, INF, sizeof(dis));
22     memset(gap, 0, sizeof(gap));
23     gap[0]++; dis[T] = 0;
24     while(!que.empty()) {
25         int u = que.front(); que.pop();
26         for(int i = head[u]; ~i; i = edge[i].nxt) {
27             int v = edge[i].v;
28             if(dis[v] == INF) {
29                 dis[v] = dis[u] + 1;
30                 gap[dis[v]]++;
31                 que.push(v);
32             }
33         }
34     }
35 }
36 
37 int ISAP(int S, int T, int n) {
38     BFS(S, T);
39     memcpy(cur, head, sizeof(cur));
40     int u = pre[S] = S, i, index, flow, ans = 0;
41     while(dis[S] < n) {
42         if(u == T) {
43             flow = INF, index = S; // index = S !!!
44             for(i = S; i != T; i = edge[cur[i]].v)
45                 if(flow > edge[cur[i]].cap) flow = edge[cur[i]].cap, index = i;
46             for(i = S; i != T; i = edge[cur[i]].v)
47                 edge[cur[i]].cap -= flow, edge[cur[i]^1].cap += flow;
48             ans += flow, u = index;
49         }
50         for(i = cur[u]; ~i; i = edge[i].nxt)
51             if(edge[i].cap > 0 && dis[edge[i].v] == dis[u] - 1) break;
52         if(~i) {
53             pre[edge[i].v] = u; cur[u] = i; u = edge[i].v;
54         } else {
55             if(--gap[dis[u]] == 0) break;
56             int md = n;
57             for(i = head[u]; ~i; i = edge[i].nxt)
58                 if(md > dis[edge[i].v] && edge[i].cap > 0) md = dis[edge[i].v], cur[u] = i;
59             gap[dis[u] = md + 1]++;
60             u = pre[u];
61         }
62     }
63     return ans;
64 }
65 
66 int main() {
67     while(~scanf("%d%d%d", &n, &m, &t)) {
68         int r = 0, l = INF;
69         memset(head, -1, sizeof(head)); tot = 0;
70         for(int i = 1; i <= m; i++) {
71             int u, v, w; scanf("%d%d%d", &u, &v, &w);
72             Add(u, v, 0, w);
73             if(r < w) r = w;
74             if(l > w) l = w;
75         }
76         int ans = r;
77         while(l <= r) {
78             int mid = (l + r) >> 1;
79             for(int i = 0; i < tot; i++)
80                 if(edge[i].w <= mid) edge[i].cap = 1;
81                 else edge[i].cap = 0;
82             if(ISAP(1, n, n) >= t) r = mid - 1, ans = mid;
83             else l = mid + 1;
84         }
85         printf("%d
", ans);
86     }
87     return 0;
88 }