HDU 2255：奔小康赚大钱（带权二分图最大匹配-KM算法）

小咪咪 2023-07-11 08:48 28阅读 0赞

# HDU 2255：奔小康赚大钱（带权二分图最大匹配-KM算法） #

[题目链接][Link 1]

**题解：**  
题目解释已经很裸了，就是带权的二分图最大匹配。  
以前也一直都没接触KM算法，一直拖到了现在。。。。。

虽然看有些视频也讲KM算法其实用的的不多，而且完全可以用最大流来解决，但是还是想着先了解了解原理，把模板熟悉熟悉

参考的这篇博客的代码：  
[https://www.cnblogs.com/wenruo/p/5264235.html][https_www.cnblogs.com_wenruo_p_5264235.html]

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #include<sstream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #define lowbit(x) x&(-x)
    #define ll long long
    #define inf 0x3f3f3f3f
    using namespace std;
    const double pi=acos(-1.0);
    const int maxn=310;
    int w[maxn][maxn];
    int lx[maxn],ly[maxn];
    int match[maxn],slack[maxn];
    int visx[maxn],visy[maxn];
    int n;
    bool dfs(int x){
        
        visx[x]=1;
        for(int y=1;y<=n;y++){
        
            if(visy[y])
                continue;
            int t=lx[x]+ly[y]-w[x][y];
            if(t==0){
        
                visy[y]=1;
                if(match[y]==0||dfs(match[y])){
        
                    match[y]=x;
                    return true;
                }
            }
            else if(slack[y]>t){
        
                slack[y]=t;
            }
        }
        return false;
    }
    int KM(){
        
        memset(lx,0,sizeof(lx));
        memset(ly,0,sizeof(ly));
        memset(match,0,sizeof(match));
        for(int i=1;i<=n;i++){
        
            for(int j=1;j<=n;j++){
        
                if(lx[i]<w[i][j])
                    lx[i]=w[i][j];
            }
        }
        for(int i=1;i<=n;i++){
        
            for(int j=1;j<=n;j++){
        
                slack[j]=inf;
            }
            while(1){
        
                memset(visx,0,sizeof(visx));
                memset(visy,0,sizeof(visy));
                if(dfs(i))
                    break;
                int d=inf;
                for(int k=1;k<=n;k++){
        
                    if(!visy[k]&&d>slack[k])
                        d=slack[k];
                }
                for(int k=1;k<=n;k++){
        
                    if(visx[k])
                        lx[k]-=d;
                    if(visy[k])
                        ly[k]+=d;
                }
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++){
        
            ans+=w[match[i]][i];
        }
        return ans;
    }
    int main(){
        
        while(~scanf("%d",&n)){
        
            for(int i=1;i<=n;i++){
        
                for(int j=1;j<=n;j++){
        
                    scanf("%d",&w[i][j]);
                }
            }
            printf("%d\n",KM());
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=2255
[https_www.cnblogs.com_wenruo_p_5264235.html]: https://www.cnblogs.com/wenruo/p/5264235.html