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