当前位置：首页 > news >正文

KM算法模板(二分图的最大权匹配)

news 来源：原创 2024/4/27 16:15:29

又掌握了一个模板~~~其实是差不多理解了，比较菜..

二次元霸主写博客就是强啊： http://www.cnblogs.com/wenruo/p/5264235.html

但...不敢想象博主是男是女。

依旧改成自己喜欢的模板格式~

//模板HDU-2255 
#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdio>

using namespace std;
const int maxn = 305;
const int inf = 0x3f3f3f3f;

int weight[maxn][maxn];
int lx[maxn], ly[maxn];
int visx[maxn], visy[maxn];
int match[maxn];
int slack[maxn];
int n;

int dfs(int cur)
{
	visx[cur] = 1;
	for(int i = 1; i <= n; ++i)
	{
		if(visy[i]) continue;
		int gap = lx[cur] + ly[i] - weight[cur][i];
		if(gap == 0)
		{
			visy[i] = 1;
			if(match[i] == -1 || dfs(match[i]))
			{
				match[i] = cur;
				return 1;
			}
		}
		else
		{
			slack[i] = min(slack[i], gap);
		}
	}
	return 0;
}

int KM()
{
	memset(match, -1, sizeof match);
	memset(ly, 0, sizeof ly);
	
	for(int i = 1; i <= n; ++i)
	{
		lx[i] = weight[i][1];
		for(int j = 2; j <= n; ++j)
		lx[i] = max(lx[i], weight[i][j]);
	}
	
	for(int i = 1; i <= n; ++i)
	{
	//	fill(slack, slack+n, inf);
		memset(slack, 0x3f, sizeof slack);
		while(1)
		{
			memset(visx, 0, sizeof visx);
			memset(visy, 0, sizeof visy);
			
			if(dfs(i)) break; 
			
			int key = inf;
			for(int j = 1; j <= n; ++j)
				if(!visy[j]) key = min(key, slack[j]);
			
			for(int j = 1; j <= n; ++j)
			{
				if(visx[j]) lx[j] -= key;
				
				if(visy[j]) ly[j] += key;
				else slack[j] -= key;
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; ++i)
	{
		ans += weight[match[i]][i];
	}
	return ans;
}
int main()
{
	while(scanf("%d", &n) != EOF)
	{
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= n; ++j)
				scanf("%d", &weight[i][j]);	
		printf("%d\n", KM());
	} 
	return 0;
}

当交这个模板题的时候T了若干次，原因是，用到了一个fill(a, a+N, k)的函数，感觉这个函数内部应该就是一个for循环赋值的效率，肯定是不如memset效率高的，唯一优点就是能填充任何值。memset按字节进行填充，只能填充0, -1, 0x3f(int范围的0x3f3f3f3f), 0x3f3f(long long范围的0x3f3f3f3f3f3f3f3f[实践证明可用]) 其他就不可以了。

fill函数可参见: http://blog.csdn.net/liuchuo/article/details/52296646

memset函数可参见: http://www.cnblogs.com/handsomecui/p/4723949.html

继续加油~