[POJ] 2112 Optimal Milking.cpp

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 999999

int K, C, M, N;  // N = K + C
int dis[500][500];

int MaxFlow(int length);
int cap[500][500], flow[500][500];
int bottleneck[500], pre[500];

int main()
{
    scanf("%d %d %d", &K, &C, &M);
    N = K + C;  // number of all nodes
    // Input
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) {
            scanf("%d", &dis[i][j]);
            if (dis[i][j] == 0)
                dis[i][j] = INF;
        }
    // Floyd
    for (int k = 0; k < N; ++k)
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);

    // Binary Search
    int left = 1, mid, right = INF;
    while (left != right) {
        mid = (left + right) / 2;
        int sum = MaxFlow(mid);

        // check if all cows arrive
        if (sum >= C) right = mid;
        else left = mid + 1;
    }
    printf("%d\n", left);

}
int MaxFlow(int max_length)
{
    // Initial
    int S = N,   // Super source
        T = N+1; // Super sink
    memset(cap, 0, sizeof(cap));
    memset(flow, 0, sizeof(flow));

    for (int i = K; i < N; ++i) // 牛與機器之間距離<=max_length的容量設為1
        for (int j = 0; j < K; ++j)
            if (dis[i][j] <= max_length) cap[i][j] = 1;
    for (int i = 0; i < K; ++i) // for all machines
        cap[i][T] = M;
    for (int i = K; i < N; ++i) // for all cows
        cap[S][i]= 1;

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

        while (!Q.empty() && !bottleneck[T]) {
            int cur = Q.front(); Q.pop();
            for (int nxt = 0; nxt < N+2; ++nxt) {
                if (bottleneck[nxt] == 0 && cap[cur][nxt] > flow[cur][nxt]) {
                    Q.push(nxt);
                    pre[nxt] = cur;
                    bottleneck[nxt] = min(bottleneck[cur], cap[cur][nxt] - flow[cur][nxt]);
                }
            }
        }
        if (bottleneck[T] == 0) break;

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