POJ 2112 二分图多重婚配+二分+floyd

POJ 2112 二分图多重匹配+二分+floyd

题目意思不在赘述

二分图多重匹配一般都可以用网络流来做，只不过网络流的代码太长。

具体看代码把

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#define MAXN 250
#define MAXM 100005
#define INF 1000000007
#define eps 1e-11
#define lch(x) x<<1
#define rch(x) x<<1|1
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
using namespace std;
int d[MAXN][MAXN];
int K, C, M;
vector<int>g[MAXN];
int match[MAXN][MAXN];
int cnt[MAXN];
bool mark[MAXN];
void floyd(int n)
{
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];
}
int dfs(int u)
{
    int size = g[u].size();
    for(int i = 0; i < size; i++)
    {
        int v = g[u][i];
        if(mark[v]) continue;
        mark[v] = 1;
        if(cnt[v] < M)  //M代表的是每个机器的容量,match存储匹配结果，cnt数组则是存每台机器已经匹配的数量
        {
            match[v][cnt[v]++] = u;
            return 1;
        }
        for(int j = 0; j < cnt[v]; j++)
            if(dfs(match[v][j]))
            {
                match[v][j] = u;
                return 1;
            }
    }
    return 0;
}
int main()
{
    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", &d[i][j]);
            if(i != j && d[i][j] == 0) d[i][j] = INF;
        }
    floyd(K + C);
    int low = 0, high = INF;
    int ans = INF;
    while(low <= high)
    {
        int mid = (low + high) >> 1;
        for(int i = 0; i < MAXN; i++) g[i].clear();
        memset(match, 0, sizeof(match));
        memset(cnt, 0, sizeof(cnt));
        for(int i = K + 1; i <= K + C; i++)
            for(int j = 1; j <= K; j++)
                if(d[i][j] <= mid)
                    g[i].push_back(j);
        int num = 0;
        for(int i = K + 1; i <= K + C; i++)
        {
            memset(mark, 0, sizeof(mark));
            num += dfs(i);
        }
        if(num == C)
        {
            high = mid - 1;
            ans = mid;
        }
        else low = mid + 1;
    }
    printf("%d\n", ans);
    return 0;
}