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

题目意思不在赘述
二分图多重匹配一般都可以用网络流来做，只不过网络流的代码太长。
具体看代码把

[cpp] 
#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)   www.zzzyk.com
        { 
            high = mid - 1; 
            ans = mid; 
        } 
        else low = mid + 1; 
    } 
    printf("%d\n", ans); 
    return 0; 
} 

补充：软件开发 , C++ ,

上一个：poj 3348 Cows
下一个：C++编程思想部分精华提取