POJ-2112 Optimal Milking二分+ネットワークストリーム

タイトル:
Kの搾乳ステーション、C頭乳牛があり、各搾乳ステーションは毎日最大M頭乳牛にサービスすることができ、乳牛から乳牛、乳牛から搾乳ステーションまで距離があり、1日ですべての乳牛に搾乳できるマッチング案の中で、最も遠い距離の最小案を選択することができる.
解法:
2分列挙によりエッジの関係を構築し,その後,すべての牛が条件を満たす場合に搾乳できるかどうかをネットワークフローで解いた.
コードは次のとおりです.

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <algorithm>

#define inf 0x3fffffff

using namespace std;



int K, C, M, idx;



int G[250][250], head[250], SS = 240, TT = 241;



int dis[250], que[250], front, tail;



struct Node {

    int v, next, cap;

}e[60000];



void Floyd() {

    for (int k = 1; k <= K+C; ++k) {

        for (int i = 1; i <= K+C; ++i) {

            for (int j = 1; j <= K+C; ++j) {

                if (G[i][k] != -1 && G[k][j] != -1) {

                    if (G[i][k] + G[k][j] < G[i][j] || G[i][j] == -1) {

                        //       -1  ，        ，      

                        G[i][j] = G[i][k] + G[k][j];

                    }

                }

            }

        }

    }

    

/*    for (int i = K+1; i <= K+C; ++i) {

        for (int j = 1; j <= K; ++j) {

            printf("%d %d = %d
", i, j, G[i][j]);

        }    

    }

    system("pause");*/

}



void addedge(int x, int v, int cap) {

    ++idx;

    e[idx].v = v, e[idx].cap = cap;

    e[idx].next = head[x];

    head[x] = idx;

}



bool bfs() {

    int pos;

    memset(dis, 0xff, sizeof (dis));

    dis[SS] = 0;

    front = tail = 0;

    que[++tail] = SS;

    while (front != tail) {

        pos = que[++front];

        for (int i = head[pos]; i != -1; i = e[i].next) {

            int v = e[i].v, cap = e[i].cap;

            if (dis[v] == -1 && cap > 0) {

                dis[v] = dis[pos] + 1;

                que[++tail] = v;

            }

        }

    }

    return dis[TT] != -1;

}



int dfs(int u, int flow) {

    if (u == TT) {

        return flow;

    }

    int tf = 0, f;

    for (int i = head[u]; i != -1; i = e[i].next) {

        int v = e[i].v, cap = e[i].cap;

        if (dis[v] == dis[u]+1 && cap > 0 && (f = dfs(v, min(cap, flow)))) {

            e[i].cap -= f, e[i^1].cap += f;

            flow -= f;

            tf += f;

        }

    }

    if (tf == 0) dis[u] = -1;

    return tf;

}



int Dinic() {

    int ret = 0;

    while (bfs()) {

        ret += dfs(SS, inf);

    }

    return ret;

}



int bsearch(int l, int r) {

    int ret;

    while (l <= r) {

        int mid = (l + r) >> 1;

        memset(head, 0xff, sizeof (head));

        idx = -1;

        for (int i = 1; i <= K; ++i) { //          

            addedge(i, TT, M);//              

            addedge(TT, i, 0);

        }

        for (int i = K+1; i <= K+C; ++i) { //         

            addedge(SS, i, 1);

            addedge(i, SS, 0);

            for (int j = 1; j <= K; ++j) { //               

                if (G[i][j] != -1 && G[i][j] <= mid) {

                    addedge(i, j, 1);

                    addedge(j, i, 0);

                }

            }

        } 

        if (Dinic() == C) {

            ret = mid;

            r = mid - 1;

        } else {

            l = mid + 1;

        }

    }

    return ret;

}



int main() {

    while (scanf("%d %d %d", &K, &C, &M) == 3) {

        //  K     ， C       

        memset(G, 0xff, sizeof (G));

        for (int i = 1; i <= K+C; ++i) {

            for (int j = 1; j <= K+C; ++j) {

                scanf("%d", &G[i][j]);

                if (G[i][j] == 0) G[i][j] = -1;

            }

        }

        Floyd();

        //      200，                   

        printf("%d
", bsearch(1, 50000));

    }

    return 0;

}