HDU - 2255 奔小康赚大钱（KM）

た入场券 2022-05-17 12:37 162阅读 0赞

#                                            奔小康赚大钱 #

### Problem Description ###

传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革：重新分配房子。  
这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住（如果有老百姓没房子住的话，容易引起不安定因素），每家必须分配到一间房子且只能得到一间房子。  
另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓都比较富裕,他们都能对每一间房子在他们的经济范围内出一定的价格,比如有3间房子,一家老百姓可以对第一间出10万,对第2间出2万,对第3间出20万.(当然是在他们的经济范围内).现在这个问题就是村领导怎样分配房子才能使收入最大.(村民即使有钱购买一间房子但不一定能买到,要看村领导分配的).

### Input ###

输入数据包含多组测试用例，每组数据的第一行输入n,表示房子的数量(也是老百姓家的数量)，接下来有n行,每行n个数表示第i个村名对第j间房出的价格(n<=300)。

### Output ###

请对每组数据输出最大的收入值，每组的输出占一行。

### Sample Input ###

100 10

15 23

### Sample Output ###

123

**题意描述：**  
领导给百姓分房子，给出类每户人家对每个房子的给出的价格，问领导的最大收益是多少。

**解题思路：**

Km算法模板题，对于km算法与二分匹配的区别为：二分匹配解决的是两个集合中的数配对使配对数最多，而km算法解决的也是两个集合进行配对只不过两集合间的组合数的权值不同km使最后配对的结果的权值和最大，在二分匹配中可以默认为权值都是相同的都为1；比如讲两集合分为x和y；km算法定义lx\[ \]数组和ly\[ \]数组及w\[ \]\[ \]数组，w数组存储每个集合x元素对每个集合y元素的权值，lx\[ \]数组初始为每个x对所有y中的最大值，ly\[ \]数组初始化为0，保证lx\[i\]+ly\[j\]>=w\[i\]\[j\]。开始进行匹配当匹配冲突后就d=lx\[i\]+ly\[j\]-w\[i\]\[j\]，对lx\[\]数组中已匹配过得点lx\[i\]进行更行lx\[i\]=lx\[i\]-d；对ly\[ \]数组中已匹配过得点进行更新ly\[j\]=ly\[j\]+d；更新后继续进行匹配，知道把所有能的点匹配完，最后循环找match\[ \]数组中存储的匹配的点，找出对应的w\[match\[i\]\]\[i\]权值加在一起的到最大权值和。

KM讲解：[https://blog.csdn.net/L\_\_emon/article/details/47451905][https_blog.csdn.net_L_emon_article_details_47451905]

#include<stdio.h>
    #include<string.h>
    # define inf 99999999
    int lx[310],ly[310],w[310][310];
    int bookx[310],booky[310],match[310];
    int num[310];
    int n;
    int dfs(int u)
    {
    	int i,t;
    	bookx[u]=1; 
    	for(i=1;i<=n;i++)
    	{
    		if(booky[i]==0)
    		{
    			t=lx[u]+ly[i]-w[u][i];
    			if(t==0)
    			{
    				booky[i]=1;
    				if(match[i]==0||dfs(match[i]))
    				{
    					match[i]=u;
    					return 1;
    				}
    			}
    			else if(num[i]>t)
    				num[i]=t;
    		}
    	}
    	return 0;
    }
    int km()
    {
    	int i,j,d,max,k,ans;
    	memset(ly,0,sizeof(ly));
    	memset(match,0,sizeof(match));
    	for(i=1;i<=n;i++)
    	{
    		max=-inf;
    		for(j=1;j<=n;j++)
    		{
    			if(max<w[i][j])
    				max=w[i][j];
    		}
    		lx[i]=max;
    	}
    	for(k=1;k<=n;k++)
    	{
    		for(i=1;i<=n;i++)
    			num[i]=inf;
    		while(1)
    		{
    			memset(bookx,0,sizeof(bookx));
    			memset(booky,0,sizeof(booky));
    			if(dfs(k))
    				break;
    			d=inf;
    			for(i=1;i<=n;i++)
    			{
    				if(booky[i]==0&&d>num[i])
    					d=num[i];
    			}
    			for(i=1;i<=n;i++)
    				if(bookx[i]==1)
    					lx[i]=lx[i]-d;
    			for(i=1;i<=n;i++)
    				if(booky[i]==1)
    					ly[i]=ly[i]+d;
    		}
    	}
    	ans=0;
    	for(i=1;i<=n;i++)
    		if(match[i]!=0)
    			ans=ans+w[match[i]][i];
    	return ans;
    }
    int main()
    {
    	int i,j,sum;
    	while(scanf("%d",&n)!=EOF)
    	{
    		for(i=1;i<=n;i++)
    			for(j=1;j<=n;j++)
    				scanf("%d",&w[i][j]);
    		sum=km();
    		printf("%d\n",sum);
    	}
    	return 0;
    }

[https_blog.csdn.net_L_emon_article_details_47451905]: https://blog.csdn.net/L__emon/article/details/47451905