自动搬运

查看原文

来自洛谷，原作者为

	薛裕龙 **

搬运于2025-08-24 21:26:28，当前版本为作者最后更新于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;
}