[POJ] 2455 Secret Milking Machine.cpp

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define INF 999999999
struct Edge{
    int u,
        v,
        len;
}E[40001];

int cap[205][205], flow[205][205];
int bottleneck[205], pre[205];
int MaxFlow(int length, int N, int P);

int main()
{
    int N, P, T;
    scanf("%d %d %d", &N, &P, &T);
    // Input
    int u, v, c, max_edge = 0;
    for (int i = 0; i < P; ++i) {
        scanf("%d %d %d", &E[i].u, &E[i].v, &E[i].len);
        max_edge = max(max_edge, E[i].len);
    }

    // Binary Search
    int left = 0, right = max_edge, mid;
    while (left != right) {
        mid = (left + right) / 2;

        if (MaxFlow(mid, N, P) >= T) right = mid;
        else left = mid + 1;
    }
    printf("%d\n", left);
}
int MaxFlow(int length, int N, int P)
{
    // build graph
    memset(cap, 0, sizeof(cap));
    memset(flow, 0, sizeof(flow));
    for (int i = 0; i < P; ++i) {
        if (E[i].len <= length)
            cap[E[i].u][E[i].v] = (cap[E[i].v][E[i].u] += 1); // 用+=因為u到v可能不只一條道路
    }

    // bfs
    int result = 0;
    while (1) {
        memset(bottleneck, 0, sizeof(bottleneck));
        queue<int> Q;
        Q.push(1);
        bottleneck[1] = INF;

        while (!Q.empty() && !bottleneck[N]) { // 記得加!bottleneck[N]優化, 不然TLE
            int cur = Q.front(); Q.pop();
            for (int nxt = 1; nxt <= N; ++nxt) {
                if (bottleneck[nxt] == 0 && cap[cur][nxt] > flow[cur][nxt]) {
                    pre[nxt] = cur;
                    Q.push(nxt);
                    bottleneck[nxt] = min(bottleneck[cur], cap[cur][nxt] - flow[cur][nxt]);
                }
            }
        }
        if (bottleneck[N] == 0) break;

        for (int cur = N; cur != 1; cur = pre[cur]) {
            flow[pre[cur]][cur] += bottleneck[N];
            flow[cur][pre[cur]] -= bottleneck[N];
        }
        result += bottleneck[N];
    }
    return result;
}