POJ-2112: Optimal Milking

keyword

最大流　二分探索　C++

問題概要

K(<30)個の搾乳機とC(<200)匹の牛がいる。搾乳機はM(<15)匹まで同時に処理できる。各搾乳機および各牛間の距離行列が与えられる。牛が移動する距離の最大値の最小化をする問題。

解法

最大値の最小化なので定石通り二分探索する。距離の上限を決めてやると2部グラフが構成できるので、あとは2部マッチングのようにsourceから牛へ容量1の辺を張り、搾乳機からsinkへ容量Mの辺を張ってやればよい。実装時間26分。

#include <cstdio>
#include <string.h>
#include <queue>
using namespace std;

const int MAX_V = 250;
const int INF = 1<<28;
int K, C, V, M;
int graph[MAX_V][MAX_V];

bool check(int limit){
    for(int i=0; i<V+2; i++)G[i].clear();
    for(int i=0; i<K; i++){
        add_edge(i,V+1,M);
    }
    for(int i=K; i<V; i++){
        add_edge(V,i,1);
    }
    for(int i=0; i<K; i++){
        for(int j=K; j<V; j++)if(graph[i][j]<=limit){
            add_edge(j,i,1);
        }
    }
    return max_flow(V,V+1)==C;
}

int solve(){
    for(int k=0; k<V; k++)for(int i=0; i<V; i++)for(int j=0; j<V; j++){
        graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
    }
    int low=0, high=1<<20;
    while(high - low > 1){
        int mid = (high+low)/2;
        if(check(mid)) high = mid;
        else low = mid;
    }
    return high;
}

int main(){
    scanf("%d%d%d",&K,&C,&M);
    V = K + C;
    for(int i=0; i<K+C; i++){
        for(int j=0; j<K+C; j++){
            int x;
            scanf("%d",&x);
            graph[i][j] = x?x:INF;
        }
    }
    printf("%d\n",solve());
    return 0;
}