POJ 2112 Optimal Milking[網絡流+二分+最短路]

求使所有牛都可以被擠牛奶的條件下牛走的最長距離。

Floyd求出兩兩節點之間的最短路，然後二分距離。

構圖：

將每一個milking machine與源點連接，邊權為最大值m，每個cow與匯點連接，邊權為1，然後根據二分的距離x，將g[i][j] < x的milking machine節點i與cow節點j連接，邊權為1，其他的賦值為零。

最大流的結果是可以被擠奶的cow數量，判斷是否等於總的cow總量即可。

[cpp] #include <iostream>  
#include <cstring>  
#include <vector>  
#include <cstdio>  
#include <algorithm>  
using namespace std; 
#define N 240  
#define INF 0x3f3f3f3f  
 
class Dinic { 
public: 
    int n, s, t, l[N], c[N][N], e[N]; 
    int flow(int maxf = INF) { 
        int left = maxf; 
        while (build()) left -= push(s, left); 
        return maxf - left; 
    } 
    int push(int x, int f) { 
        if (x == t) return f; 
        int &y = e[x], sum = f; 
        for (; y<n; y++) 
            if (c[x][y] > 0 && l[x]+1==l[y]) { 
                int cnt = push(y, min(sum, c[x][y])); 
                c[x][y] -= cnt; 
                c[y][x] += cnt; 
                sum -= cnt; 
                if (!sum) return f; 
            } 
        return f-sum; 
    } 
    bool build() { 
        int m = 0; 
        memset(l, -1, sizeof(l)); 
        l[e[m++]=s] = 0; 
        for (int i=0; i<m; i++) for (int y=0; y<n; y++) 
            if (c[e[i]][y] > 0 && l[y]<0) l[e[m++]=y] = l[e[i]] + 1; 
        memset(e, 0, sizeof(e)); 
        return l[t] >= 0; 
    } 
} net; 
int g[N][N], n, k, c, m; 
 
bool ok(int x) { 
    memset(net.c, 0, sizeof(net.c)); 
    net.s = 0, net.t = n + 1, net.n = n + 2; 
 
    for (int i=1; i<=k; i++) net.c[0][i] = m; 
    for (int i=k+1; i<=n; i++) net.c[i][net.t] = 1; 
 
    for (int i=1; i<=k; i++) 
        for (int j=k+1; j<=n; j++) 
            if (g[i][j] <= x) net.c[i][j] = 1; 
            else net.c[i][j] = 0; 
 
    return net.flow() == c; 
} 
int main() { 
 
    while (scanf("%d%d%d", &k, &c, &m) == 3) { 
        n = k + c; 
        for (int i=1; i<=n; i++) 
            for (int j=1; j<=n; j++) { 
                scanf(" %d", &g[i][j]); 
                if (g[i][j] == 0 && i != j) g[i][j] = INF; 
            } 
        for (int p=1; p<=n; p++) for (int i=1; i<=n; i++) 
            for (int j=1; j<=n; j++) g[i][j] = min(g[i][j], g[i][p] + g[p][j]); 
 
        int l = 0, r = INF, mid, ans; 
        while (l <= r) { 
            mid = (l + r) >> 1; 
            if (ok(mid)) { 
                ans = mid; 
                r = mid -1; 
            } else l = mid + 1; 
        } 
        cout << ans << endl; 
    } 
    return 0; 
}