本文主要是介绍hdu2255，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：点击打开链接
题意：给一个n*n的矩阵,每个数表示第i个村名对第j间房出的价格，问最后最大价格是多少
代码：
#include <iostream>
#include <climits> //这个头文件含有int的上限，因此可以调用INT_MAX
#include <string.h> //INT_MAX=2147483647
#include <stdio.h>
#include <algorithm>
using namespace std;
int s[305][305],match[305],visx[305],visy[305];
int lx[305],ly[305];
int n;
int hungarian(int x){int i,j;visx[x]=1;for(i=1;i<=n;i++){if(!visy[i]&&lx[x]+ly[i]==s[x][i]){visy[i]=1;if(!match[i]||hungarian(match[i])){match[i]=x;return 1;}}}return 0;
}
void KM(){int i,j,k,temp;memset(lx,0,sizeof(lx));memset(ly,0,sizeof(ly));for(i=1;i<=n;i++)for(j=1;j<=n;j++)lx[i]=max(lx[i],s[i][j]);for(i=1;i<=n;i++){while(1){memset(visx,0,sizeof(visx));memset(visy,0,sizeof(visy));if(hungarian(i))break;else{temp=INT_MAX;for(j=1;j<=n;j++)if(visx[j])for(k=1;k<=n;k++)if(!visy[k]&&temp>lx[j]+ly[k]-s[j][k])temp=lx[j]+ly[k]-s[j][k];for(j=1;j<=n;j++){if(visx[j])lx[j]-=temp;if(visy[j])ly[j]+=temp;}}}}
} //KM算法模板
int main(){ //这道题就是二分图最优匹配，也就用到了KM算法，我理解int i,j,sum; //的KM算法就是先全部选择最大利润的匹配，之后必然有很while(scanf("%d",&n)!=EOF){ //大几率出现有多个同时匹配一个的情况，因此之后选择移memset(match,0,sizeof(match)); //损失利润最小的情况，直到全部匹配for(i=1;i<=n;i++) //我就是看下面这个博客学习的，链接：for(j=1;j<=n;j++) //http://philoscience.iteye.com/blog/1754498scanf("%d",&s[i][j]);KM();sum=0;for(i=1;i<=n;i++)sum+=s[match[i]][i];printf("%d\n",sum);}return 0;
}
这篇关于hdu2255的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
