hdu2255 奔小康赚大钱

本文主要是介绍hdu2255 奔小康赚大钱，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接:hdu2255
题目大意：
(额题意是中文的并不是很想打呢)
多组数据
给定一个$n$，表示有$n$间房子，也表示有$n$个人。然后$n$行每行$n$个数，第$i$行表示第$i$个人对这$n$间房子给出的价格。问村长应该怎么安排哪个人买哪间房能使他的收入最大。求最大的收入值。

题解：
KM模板题
我都忘光了而已（卑微

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 310
#define inf 0x3f3f3f3fint tim,n;
int visx[maxn],visy[maxn],lx[maxn],ly[maxn];
int d[maxn][maxn],slack[maxn],bf[maxn];
int mymin(int x,int y){return (x<y)?x:y;}
int mymax(int x,int y){return (x>y)?x:y;}
bool ffind(int x)
{visx[x]=tim;for (int y=1;y<=n;y++)if (visy[y]!=tim && lx[x]+ly[y]-d[x][y]==0)//!!!!!!!!!lx[x]+ly[y]-d[x][y]==0{visy[y]=tim;if (bf[y]==-1 || ffind(bf[y])){bf[y]=x;return true;}}else slack[y]=mymin(slack[y],lx[x]+ly[y]-d[x][y]);return false;}
int KM()
{tim=0;int i,j;for (i=1;i<=n;i++)lx[i]=-inf,visx[i]=ly[i]=visy[i]=0,bf[i]=-1;for (i=1;i<=n;i++)for (j=1;j<=n;j++)lx[i]=mymax(lx[i],d[i][j]);for (i=1;i<=n;i++){for (j=1;j<=n;j++) slack[j]=inf;while(1){tim++;if (ffind(i)) break;int delta=inf;for (j=1;j<=n;j++) if (visy[j]!=tim) delta=mymin(delta,slack[j]);for (j=1;j<=n;j++){if (visx[j]==tim) lx[j]-=delta;if (visy[j]==tim) ly[j]+=delta;else slack[j]-=delta;}}}int ret=0;for (i=1;i<=n;i++)if (bf[i]!=-1) ret+=d[bf[i]][i];return ret;
}
int main()
{int i,j;while (cin>>n){memset(d,0,sizeof(d));for (i=1;i<=n;i++)for (j=1;j<=n;j++)scanf("%d",&d[i][j]);printf("%d\n",KM());}return 0;}

这篇关于hdu2255 奔小康赚大钱的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---