POJ 2112 Optimal Milking 二分枚舉 + 最大流

Optimal Milking

Time Limit: 2000MS	Memory Limit: 30000K
Total Submissions: 14311	Accepted: 5148
Case Time Limit: 1000MS

Description

FJ has moved his K (1 <= K <= 30) milking machines out into the cow pastures among the C (1 <= C <= 200) cows. A set of paths of various lengths runs among the cows and the milking machines. The milking machine locations are named by ID numbers 1..K; the cow locations are named by ID numbers K+1..K+C. 

Each milking point can "process" at most M (1 <= M <= 15) cows each day. 

Write a program to find an assignment for each cow to some milking machine so that the distance the furthest-walking cow travels is minimized (and, of course, the milking machines are not overutilized). At least one legal assignment is possible for all input data sets. Cows can traverse several paths on the way to their milking machine. 

Input

* Line 1: A single line with three space-separated integers: K, C, and M. 

* Lines 2.. ...: Each of these K+C lines of K+C space-separated integers describes the distances between pairs of various entities. The input forms a symmetric matrix. Line 2 tells the distances from milking machine 1 to each of the other entities; line 3 tells the distances from machine 2 to each of the other entities, and so on. Distances of entities directly connected by a path are positive integers no larger than 200. Entities not directly connected by a path have a distance of 0. The distance from an entity to itself (i.e., all numbers on the diagonal) is also given as 0. To keep the input lines of reasonable length, when K+C > 15, a row is broken into successive lines of 15 numbers and a potentially shorter line to finish up a row. Each new row begins on its own line. 

Output

A single line with a single integer that is the minimum possible total distance for the furthest walking cow. 

Sample Input

2 3 2
0 3 2 1 1
3 0 3 2 0
2 3 0 1 0
1 2 1 0 2
1 0 0 2 0
      

Sample Output

2      

總結：二分的用法真是廣泛，腦動大開      

//二分枚舉加最大流
//要先預處理一下每兩個物體之間的最短路徑，floyd算法
//從源點連接配接每個機器，容量為m，然後連接配接牛和彙點，容量為1。然後枚舉邊的長度，當機器和牛的距離小于等于枚舉的邊的長度時，連接配接它們，容量為1，然後求最大流，此時最大流的結果是最多有多少頭牛被擠奶。如果結果為c，那麼就是滿足條件的。用二分找出最小符合條件的就是最終答案
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <cctype>
#include <vector>
using namespace std;

const int N = 300;
const int INF = 0x3f3f3f3f;
struct edge
{
    int to, cap, rev;
};
vector <edge> G[N];
int level[N], iter[N];
int s[N][N];

void add_edge(int from, int to, int cap)
{
    edge e;
    e.to = to, e.cap = cap, e.rev = G[to].size();
    G[from].push_back(e);
    e.to = from, e.cap = 0, e.rev = G[from].size() - 1;
    G[to].push_back(e);
}

void bfs(int s)
{
    memset(level, -1, sizeof level);
    queue <int> que;
    que.push(s);
    level[s] = 0;

    while(! que.empty())
    {
        int v = que.front(); que.pop();
        for(int i = 0; i < G[v].size(); i++)
        {
            edge &e = G[v][i];
            if(e.cap > 0 && level[e.to] < 0)
            {
                level[e.to] = level[v] + 1;
                que.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 max_flow(int s, int t)
{
    int flow = 0, f;
    while(true)
    {
        bfs(s);
        if(level[t] < 0) return flow;
        memset(iter, 0, sizeof iter);
        while(f = dfs(s, t, INF), f > 0)
            flow += f;
    }
}

int main()
{
    int k, c, m;

    while(~ scanf("%d%d%d", &k, &c, &m))
    {
        for(int i = 1; i <= k + c; i++)
            for(int j = 1; j <= k + c; j++)
            {
                scanf("%d", &s[i][j]);
                if(i != j && s[i][j] == 0) s[i][j] = INF;
            }

        for(int g = 1; g <= k + c; g++) //floyd算法預處理最短路徑
            for(int i = 1; i <= k + c; i++)
                for(int j = 1; j <= k + c; j++)
                    s[i][j] = min(s[i][j], s[i][g] + s[g][j]);

        int l = 0, r = INF, mid, res;
        while(l <= r) //二分枚舉
        {
            for(int i = 1; i <= k; i++)
                add_edge(0, i, m);
            for(int i = k + 1; i <= k + c; i++)
                add_edge(i, k + c + 1, 1);

            mid = (l + r) >> 1;
            for(int i = 1; i <= k; i++)
                for(int j = k + 1; j <= k + c; j++)
                    if(s[i][j] <= mid)
                        add_edge(i, j, 1);

            if(max_flow(0, k + c + 1) == c) res = mid, r = mid - 1; //最大流
            else l = mid + 1;

            for(int i = 0; i <= k + c + 1; i++)
                G[i].clear();
        }
        printf("%d\n", res);
    }

    return 0;
}