二分图多重匹配(Poj 3189)

一般二分图匹配中，在一个匹配中，二分图中的 X 部与 Y 部中的点是一对一的。二分图多重匹配中，X 部中的点可以匹配多个 Y 部中的点, Y 部中的点最多只能匹配一个 X 部中的点。

这个问题可以建立网络流模型，用网络流算法解决。但更为简单的方法是用二分图最大匹配的匈牙利算法的一些变动来解决，方法详见代码。

 

Poj 3189:

题意为有 N 条牛和 B 个牛棚，每个牛棚有一个限制 C[i]，表示最多能关 C[i] 条牛，每条牛对每个牛棚有一个喜爱值，用1 到 B 表示。现在让你安排这些牛，使得牛棚中的牛对牛棚的最大喜爱值与最小喜爱值的差值最小。

 

基本方法为枚举这个差值，然后判断能否有一种安排方案。枚举方法用两个指针 head, tail，初始化 head= tail= 1, head 表示最小喜爱值，tail 表示最大喜爱值。如果喜爱值在 [head, tail]范围内可以安排牛，则将 head++，增加最小喜爱值，减少差值，否则 tail++，增加最大喜爱值，增加差值。枚举过程中寻找最小差值。

如何判定是否有安排方案则要用到二分图的多重匹配。如果牛 i 对牛棚 j 的喜爱值在 [head, tail]范围内，则将 i 与 j 连一条边，就构造了一个二分图多重匹配的模型。

 

代码：

#include <stdio.h>

int const N= 1010, B= 21;
int n, b, head, tail;
int mat[N][B], mth[B][N], flag[B], cap[B], C[B];

int dfs( int x ){ // 二分图多重匹配

    for( int i= 1; i<= b; ++i )
    if( head<= mat[x][i] && mat[x][i]<= tail && !flag[i] ){
        flag[i]= 1;
        
        if( cap[i] ){
            cap[i]--;
            mth[i][ ++mth[i][0] ]= x; // mth[i][0] 保存当前已经匹配的数量

            return 1;
        }
        else{
            for( int j= 1; j<= mth[i][0]; ++j )
            if( dfs( mth[i][j] ) ){ // 寻找增广路径

                mth[i][j]= x;
                return 1;
            }
        }
    }
    return 0;
}

int max_match(){
    for( int i= 0; i<= B; ++i ){
        cap[i]= C[i]; mth[i][0]= 0; }
    int ans= 0;
    for( int i= 1; i<= n; ++i ){
        for( int j= 0; j<= b; ++j ) flag[j]= 0;
        ans+= dfs(i);
    }
    return ans;
}

void solve(){
    head= 1; tail= 1;
    int ans= b;
    while( head<= tail && tail<= b ){
        if( max_match()== n ) {
            if( tail- head+ 1< ans ) ans= tail- head+ 1;
            head++;
        }
        else tail++;
    }
    printf("%d\n", ans );
}

int main(){
    scanf("%d%d",&n,&b);
    for( int i= 1; i<= n; ++i )
    for( int j= 1; j<= b; ++j ){
        int x;
        scanf("%d",&x );
        mat[i][x]= j;
    }
    for( int i= 1; i<= b; ++i ) scanf("%d", C+ i );
    solve();
    
    return 0;
}