Optimal Milking---poj2112（多重匹配+Floyd+二分）

题意：K个挤奶器（编号1~K），每个挤奶器每天最多供M头奶牛。共有C头奶牛（编号K+1~K+C）。挤奶器和奶牛间有不同长度的路。

编写程序，寻找一个方案，安排每头牛到某个挤奶器挤奶，并使得C头奶牛需要走的所有路程的最大路程最小。答案可以用二分来找；

一对多的二分图的多重匹配。二分图的多重匹配算法的实现类似于匈牙利算法，对于集合x中的元素xi，找到一个与其相连的元素yi后（本题中要满足相连并且距离要小于某个距离），检查匈牙利算法的两个条件是否成立，若yi未被匹配，则将

xi，yi匹配。否则，如果与yi匹配的元素已经达到上限，那么在所有与yi匹配的元素中选择一个元素，检查是否能找到一条增广路径，如果能，则让出位置，让xi与yi匹配。

Cows can traverse several paths on the way to their milking machine. 这句话说明了牛可以通过任何路径到达挤奶机，所以要用Floyd更新距离；

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<stack>
#include<map>
using namespace std;
#define N 1510
#define INF 0x3f3f3f3f
#define met(a, b) memset(a, b, sizeof(a))

int G[N][N], vis[N];
int M, K, C;

struct node
{
    int k;
    int a[N];
}Linky[N];

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++)
        G[i][j] = min(G[i][j], G[i][k]+G[k][j]);
}

bool Find(int u, int Limit)
{
    for(int i=1; i<=K; i++)
    {
        if( !vis[i] && G[u][i] <= Limit)///距离应在Limit范围之内；
        {
            vis[i] = 1;
            if( Linky[i].k < M )///当与i相连的点的个数小于M个时，直接放进来；
            {
                Linky[i].a[ Linky[i].k++ ] = u;
                return true;
            }
            for(int j=0; j<Linky[i].k; j++)///否则就看是否能替换掉其中的一个
            {
                if(Find(Linky[i].a[j], Limit))
                {
                    Linky[i].a[j] = u;
                    return true;
                }
            }
        }
    }
    return false;
}

bool Hungary(int Limit)
{
    met(Linky, 0);
    for(int i=K+1; i<=K+C; i++)
    {
        met(vis, 0);
        if( !Find(i, Limit) )///当有一个牛找不到与之相对的挤奶机时，就说明这个Limit不符合条件；
            return false;
    }
    return true;
}

int solve()
{
    int L = 0, R = INF, ans = INF;
    while(L <= R)
    {
        int Mid = (L+R)/2;
        if(Hungary(Mid))
        {
            ans = Mid;///不断更新符合条件的答案；
            R = Mid-1;
        }
        else
            L = Mid+1;
    }
    return ans;
}

int main()
{
    while(scanf("%d %d %d", &K, &C, &M) != EOF)
    {
        met(G, 0);

        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] = INF;
            }
        }

        Floyd();///Floyd求出，各点之间的距离；

        int ans = solve();

        printf("%d
", ans);
    }
    return 0;
}

View Code