POJ 2112 Optimal Milking：Floyd + 最大流 + 二分答案

题目大意

K 台挤奶机（K≤30），C 头奶牛（C≤200），每机每天最多挤 M 头（M≤15）。奶牛与机器间有多条路径。安排每头奶牛到一台机器，使所有奶牛路径中最大距离最小化。

解法框架

1. Floyd-Warshall：预处理任意两点最短距离
2. 二分最大距离 D：检查是否存在安排使所有奶牛距离 ≤ D
3. 最大流验证：
   • 源点 → 奶牛（容量 1）
   • 奶牛 → 机器（距离 ≤ D 时容量 1）
   • 机器 → 汇点（容量 M）
   • 最大流 = C 则可行

ISAP 最大流模板

struct Edge { int from, to, cap, flow; };
vector edges;
vector G[MAXN];
int gap[MAXN], d[MAXN], cur[MAXN], p[MAXN];

void addEdge(int u, int v, int c) {
    edges.push_back({u,v,c,0});
    edges.push_back({v,u,0,0});
    G[u].push_back(edges.size()-2);
    G[v].push_back(edges.size()-1);
}

int ISAP(int s, int t, int N) {
    // 标准 ISAP 实现（略）
    // 返回最大流值
}

完整流程

int main() {
    int K, C, M;
    while (cin >> K >> C >> M) {
        int N = K + C;
        // 读取邻接矩阵，0 表示不通，置 INF
        // Floyd 求全对最短路
        // 记录最大距离 maxD
        int lo = 0, hi = maxD;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            buildGraph(mid); // 根据 mid 建流网络
            if (ISAP(S, T, V) == C) hi = mid;
            else lo = mid + 1;
        }
        cout << lo << endl;
    }
}

复杂度分析

• Floyd：O((K+C)³) ≤ 230³ ≈ 1.2e7
• 二分：log(maxD) ≤ 20
• 每次 ISAP：O(V²E) 实际极快（V≤232, E≤K×C+K+C≈6000）
• 总时间：~1s 内通过

关键细节

1. 多测试用例循环读取
2. 距离 0 表示无边，Floyd 前置为 INF
3. 二分上界取 Floyd 后的最大有限距离
4. 流网络每次重建，清空 edges 和 G