KM算法，解决带边权的二分图匹配问题。
求得最大边权匹配。

参考博客： KM证明
参考博客： KM算法详解+模板
参考视频： b站视频 小姐姐声音好听(有听下去的动力)

直接上题
传送门 hdu 奔小康赚大钱
题目大意是
每组数据的第一行输入n,表示房子的数量(也是老百姓家的数量)，接下来有n行,每行n个数表示第i个村名对第j间房出的价格

然后其实就可以应用KM算法，直接跑一遍就行。。

注意多组数据

参考代码：

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 400 ;

int n,m;
int g[N][N] ;
int match[N],el[N],er[N],sl[N] ;
bool stl[N],str[N] ;

bool dfs(int u){
    stl[u] = 1 ;
    for(int i = 1;  i <= n; i++){
        if(str[i]) continue ;

        int d = el[u] + er[i] - g[u][i] ;
        if(!d){
            str[i] = 1 ;
            int t = match[i] ;
            if(!t || dfs(t)){
                match[i] = u ;
                return 1 ;
            }   
        }
        else sl[i] = min(sl[i],d) ;
    }
    return 0 ;
}


int km(){
    memset(match,0,sizeof match) ;  //初始化
    memset(er,0,sizeof er) ;
    memset(el,0,sizeof el) ;

    for(int i = 1;  i<= n ; i++){
        for(int j = 1;  j <= n ;j++){
            el[i] = max(el[i],g[i][j]) ;  //将左边的期望置为最大值
        }
    }

    for(int i = 1 ; i <= n ; i++){
        memset(sl,0x3f,sizeof sl) ;

        while(1){
            memset(stl,0,sizeof stl) ;
            memset(str,0,sizeof str) ;

            if(dfs(i)) break ;   //可以找到匹配

            int d = 0x3f3f3f3f ;   
            for(int j = 1 ; j <= n ; j++){
                if(!str[j]) d = min(d,sl[j]) ;
            }

            for(int j = 1;  j <= n ; j++){

                if(stl[j]) el[j] -= d;
                if(str[j]) er[j] += d;
                else sl[j] -= d ;
            }
        }
    }

    int res = 0 ;
    for(int i = 1;  i <= n ; i++){  
        res += g[match[i]][i] ;
    }
    return res ;
}


int main(){

    while(~scanf("%d",&n)){  //读入数据，
        for(int i = 1 ; i <= n ; i++) {
            for(int j = 1 ; j <= n; j++){
                scanf("%d",&g[i][j]) ;
            }
        }


        printf("%d\n",km()) ;
    }
    return 0;
}

推荐想象再看第二题题解

hdu Assignment

题目大意

这里共有n个员工m种工作，每个员工做m种工作是有不同的收益的。
题目中会给出初始状态下有一个匹配。

询问当前匹配与最大匹配最少修改的匹配数，与最大匹配相差多少。

设最大匹配为x
那么可以将每个权值都乘以 （n + 1）
然后将初始匹配态的边权都加上1
那么现在求得最大匹配值应该是范围在M = x (n + 1 ) ~~ x(n + 1) + n

等于 x * (n + 1) 情况是没有使用初始状态边
等于 x * （n + 1） + n是使用了n个初始状态边

发现
那么x = M / (n + 1);
包含原先边数为t = M % (n + 1 );
那么修改数为n - t ;

参考代码

//https://acm.hdu.edu.cn/showproblem.php?pid=2853
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 100;

int n,m ,mod ;
int g[N][N] ;
int match[N],el[N],er[N] ;
bool stl[N],str[N] ;
int cnt ,sl ;

void init(){
    memset(match,0,sizeof match) ;
    memset(el,0,sizeof el) ;
    memset(er,0,sizeof er) ;
}

bool dfs(int u){
    stl[u] = 1 ;
    for(int i = 1;  i <= m ; i++){  //注意这里要枚举m，枚举的是工作个数
        if(str[i]) continue ;

        int d = el[u] + er[i] - g[u][i] ;
        if(!d){
            str[i] = 1 ;
            int t = match[i] ;

            if(!t || dfs(t)){
                match[i] = u ;
                return 1; 
            }
        } 
        else sl = min(sl,d);
    }
    return 0 ;
}


void km(){
    init() ;

    for(int i = 1; i <= n ; i++){
        for(int j = 1; j <= m ; j++){
            el[i] = max(el[i],g[i][j]) ;
        }
    }


    for(int i = 1; i <= n ; i++){
        while(1){
            memset(stl,0,sizeof stl) ;
            memset(str,0,sizeof str) ;

            sl = 0x3f3f3f3f ;

            if(dfs(i)) break ;

            for(int j = 1 ; j <= n ; j++){
                if(stl[j]) el[j] -= sl ;
            }

            for(int j = 1;  j <= m ; j++){//注意这里要枚举m，枚举的是工作个数
                if(str[j]) er[j] += sl ;
            }
        }
    }


    int res = 0 ;
    for(int i = 1 ; i <= m ; i++){   //注意这里要枚举m，枚举的是工作个数，因为是记录match是工作对应人
        if(match[i])
            res += g[match[i]][i] ;
    }

    int x = res / mod ;

    printf("%d %d\n",n - res % mod, x - cnt) ;
}

int main(){
    while(~scanf("%d%d",&n,&m)){
        mod = n + 1 ;

        for(int i = 1 ; i <= n ; i++){
            for(int j = 1; j <= m ; j++){
                scanf("%d",&g[i][j]) ;  
                g[i][j] *= mod ;  //将权值都乘 (n + 1);
            }
        }

        cnt = 0 ;
        for(int i = 1; i <= n ; i++){
            int x;
            scanf("%d",&x) ;
            cnt += g[i][x] / mod ;  //记录初始状态的最大匹配
            g[i][x] += 1;    //将初始状态边权值加一
        }

        km() ;

    }
    return 0;
}