題目意思不在贅述
二分圖多重匹配一般都可以用網絡流來做，只不過網絡流的代碼太長。
具體看代碼把
[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.2cto.com
{
high = mid - 1;
ans = mid;
}
else low = mid + 1;
}
printf("%d\n", ans);
return 0;
}
