Description
传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革：重新分配房子。
这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住（如果有老百姓没房子住的话，容易引起不安定因素），每家必须分配到一间房子且只能得到一间房子。
另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓都比较富裕,他们都能对每一间房子在他们的经济范围内出一定的价格,比如有3间房子,一家老百姓可以对第一间出10万,对第2间出2万,对第3间出20万.(当然是在他们的经济范围内).现在这个问题就是村领导怎样分配房子才能使收入最大.(村民即使有钱购买一间房子但不一定能买到,要看村领导分配的).
这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住（如果有老百姓没房子住的话，容易引起不安定因素），每家必须分配到一间房子且只能得到一间房子。
另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓都比较富裕,他们都能对每一间房子在他们的经济范围内出一定的价格,比如有3间房子,一家老百姓可以对第一间出10万,对第2间出2万,对第3间出20万.(当然是在他们的经济范围内).现在这个问题就是村领导怎样分配房子才能使收入最大.(村民即使有钱购买一间房子但不一定能买到,要看村领导分配的).
Input
输入数据包含多组测试用例，每组数据的第一行输入n,表示房子的数量(也是老百姓家的数量)，接下来有n行,每行n个数表示第i个村名对第j间房出的价格(n<=300)。
Output
请对每组数据输出最大的收入值，每组的输出占一行。
题意不解释了，就是km算法的模板，然而km算法理解起来其实有一定难度（理解了整整两天路过）。
代码里有简单注解，算法具体我会另起一个单独讲解
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m;
int w[505][505];
int slack[505];
int lx[505],ly[505];
int girl[1005];
bool visx[1005],visy[1005];
int dfs(int x)
{
visx[x]=1;
for(int i=1; i<=n; i++)
{
if(!visy[i])
{
int t=lx[x]+ly[i]-w[x][i];
if(t==0) //判断该边是否被加入二分子图中
{
visy[i]=1;
if(girl[i]==-1||dfs(girl[i]))
{
girl[i]=x;
return 1;
}
}
else if(slack[i]>t) //更新y中未被加入的最大边
{
slack[i]=t;
}
}
}
return 0;
}
int km()
{
memset(girl,-1,sizeof(girl));
memset(ly,0,sizeof(ly));
for (int i = 1; i <= n; i ++)
{
lx[i]=-inf;
for (int j = 1; j <= n; j ++) //初始化最大边
if (w[i][j] > lx[i])
lx[i] = w[i][j];
}
for(int x=1; x<=n; x++)
{
for(int j=1; j<=n; j++)
slack[j]=inf;
while(1)
{
memset(visx,0,sizeof(visx));
memset(visy,0,sizeof(visy));
if(dfs(x))
{
break;
}
//加边 注意 麻蛋这个操作其实就是加边，网上的东西不厚道都不说╮(╯_╰)╭不要被迷惑
//方法为：将所有在增广轨中（就是在增广过程中遍历到）的X方点的标号全部减去一个常数d，
//所有在增广轨中的Y方点的标号全部加上一个常数d
int d = inf;
for (int i = 1; i <= n; i ++)
if (!visy[i]&&d > slack[i])
d = slack[i];
for(int i=1; i<=n; i++)
{
if(visx[i]) lx[i]-=d;
if(visy[i]) ly[i]+=d;
else
slack[i]-=d;
}
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(girl[i]>-1)
ans+=w[girl[i]][i];
}
return ans;
}
int main()
{
int x,y;
while(scanf("%d",&n)!=EOF)
{
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;
}