题解 P1559 【运动员最佳匹配问题】

薛裕龙 · 2018-07-23 10:46:40 · 题解

通过我仔细的观察，下面只有一篇是用了km算法，但是并不是c++，那我就来写一篇c++的KM算法吧。 这就是一道KM的裸题，边权就是P[i][j]* Q[i][j]，然后跑一边KM，这道题就完啦。

不要问KM算法啥玩意，那应该是在博客里学习的内容。

这个写的可以(https://www.cnblogs.com/wenruo/p/5264235.html)

但是我写的要比他简洁一点，仔细看看过程吧。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int a[25][25];//边权
int lx[25],ly[25];//顶标
int visx[25],visy[25];//标记
int pi[25];//记录匹配对象
int n;
int minz;//记录最小的改变量
bool dfs(int s){
    visx[s]=1;
    for(int i=1;i<=n;i++)
        if(!visy[i]){
            int t=lx[s]+ly[i]-a[s][i];
            if(t==0){
                visy[i]=1;
                if(pi[i]==0||dfs(pi[i])){
                    pi[i]=s;
                    return true;
                }
            }else if(t>0){
                minz=min(minz,t);
            }
        }
    return false;
}
void km(){
    for(int i=1;i<=n;i++){
        while(1){
            minz=100000000;
            memset(visx,0,sizeof(visx));
            memset(visy,0,sizeof(visy));
            if(dfs(i))break;
            for(int j=1;j<=n;j++)
            if(visx[j])lx[j]-=minz;
            for(int j=1;j<=n;j++)
            if(visy[j])ly[j]+=minz;
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            int r;
            scanf("%d",&r);
            a[j][i]*=r;
            //这个肯定是要倒过来的，仔细读题
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            lx[i]=max(lx[i],a[i][j]);//顶标预处理
    km();
    int ans=0;
    for(int i=1;i<=n;i++)
        ans+=a[pi[i]][i];//累加答案
    printf("%d",ans);
    return 0;
}