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;
}