POJ 2112 最優擠奶距離：二分答案 + 最大流判定

題目大意

K 台機器，M 隻牛。每台機器每天最多擠 K 隻牛（題目參數同名易混淆，實為每台機器產能）。牛與機器間有距離矩陣。求：滿足所有牛被擠奶的前提下，牛到其分配機器的最大距離最小化。

解題框架：二分距離 + 最大流檢查

1. Floyd 算法：計算所有點對最短距離（牛可經過其他點間接到達機器）
2. 二分答案：在 [0, MAX_DIST] 範圍二分最大允許距離 mid
3. 構建流網絡判定：
   • 源點 S 連機器，容量 = 機器產能 K
   • 機器連牛：若 dist[機器][牛] ≤ mid，容量 1
   • 牛連匯點 T，容量 1
   • 最大流 = M → 可行；否則不可行

完整代碼實現

#include <queue>
#include <vector>
#include <cstring>
#include <iostream>
#include <functional>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 250;

struct Edge {
    int to, cap, rev;
    Edge(int a, int b, int c) : to(a), cap(b), rev(c) {}
};

vector<Edge> G[MAXN];
int level[MAXN], iter[MAXN];

void addEdge(int from, int to, int cap) {
    G[from].push_back(Edge(to, cap, G[to].size()));
    G[to].push_back(Edge(from, 0, G[from].size() - 1));
}

void bfs(int s) {
    memset(level, -1, sizeof(level));
    queue<int> q;
    level[s] = 0; q.push(s);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (auto &e : G[v]) {
            if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[v] + 1;
                q.push(e.to);
            }
        }
    }
}

int dfs(int v, int t, int f) {
    if (v == t) return f;
    for (int &i = iter[v]; i < G[v].size(); ++i) {
        Edge &e = G[v][i];
        if (e.cap > 0 && level[v] < level[e.to]) {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int maxFlow(int s, int t) {
    int flow = 0;
    while (true) {
        bfs(s);
        if (level[t] < 0) return flow;
        memset(iter, 0, sizeof(iter));
        int f;
        while ((f = dfs(s, t, INF)) > 0) flow += f;
    }
}

int dist[MAXN][MAXN];
int n, m, k;  // n 機器數，m 牛數，k 機器產能

void floyd() {
    for (int k = 1; k <= n + m; ++k)
        for (int i = 1; i <= n + m; ++i)
            for (int j = 1; j <= n + m; ++j)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

bool check(int mid) {
    int S = 0, T = n + m + 1;
    for (int i = 0; i <= T; ++i) G[i].clear();
    
    // 源點連機器
    for (int i = 1; i <= n; ++i)
        addEdge(S, i, k);
    
    // 牛連匯點
    for (int i = n + 1; i <= n + m; ++i)
        addEdge(i, T, 1);
    
    // 機器連牛（距離 ≤ mid）
    for (int i = 1; i <= n; ++i)
        for (int j = n + 1; j <= n + m; ++j)
            if (dist[i][j] <= mid)
                addEdge(i, j, 1);
    
    return maxFlow(S, T) == m;
}

int main() {
    while (cin >> n >> m >> k) {
        // 讀取距離矩陣
        for (int i = 1; i <= n + m; ++i) {
            for (int j = 1; j <= n + m; ++j) {
                int x; cin >> x;
                if (i == j) dist[i][j] = 0;
                else if (x == 0) dist[i][j] = INF;
                else dist[i][j] = x;
            }
        }
        
        floyd();
        
        int lo = 0, hi = 10010;
        while (hi - lo > 1) {
            int mid = (lo + hi) >> 1;
            if (check(mid)) hi = mid;
            else lo = mid;
        }
        cout << hi << endl;
    }
    return 0;
}

關鍵點解析

複雜度分析

• Floyd：O((N+M)³)，N+M ≤ 200 可接受
• 二分：O(log MAX_DIST) ≈ 14 次
• 每次 Dinic：O(E√V)，V ≈ 200, E ≈ N×M ≤ 10⁴
• 總體：O((N+M)³ + logD · E√V)，輕鬆通過

這道題完美展示了「二分答案 + 流網絡判定」的經典套路：將優化目標轉化為決策問題，用最大流檢查可行性，再二分逼近最優值。