KM模板最大权匹配（广搜版） Luogu P1559 运动员最佳匹配问题

KM板题：

#include <bits/stdc++.h>

using namespace std;

inline void read(int &num)

{

	char ch; num = 0; int flag = 1;

	while((ch=getchar()) < '0' || ch > '9')if(ch == '-') flag = -flag;

	while(ch >= '0' && ch <= '9') num = num*10 + ch-'0', ch = getchar();

	num *= flag;

}

const int MAXN = 25;

int n, m, w[MAXN][MAXN], x, cy[MAXN], dbx[MAXN], dby[MAXN], pre[MAXN], slk[MAXN];

bool vis[MAXN];

void bfs(int now)

{

	memset(vis, 0, sizeof vis);

	memset(slk, 0x3f, sizeof slk);

	int x, y = 0, Minloc;

	cy[y] = now;

	do {

		x = cy[y]; vis[y] = 1; Minloc = 0;

		for(int i = 1; i <= n; i++) if(!vis[i])

		{

			if(dbx[x]+dby[i]-w[x][i] < slk[i]) slk[i] = dbx[x]+dby[i]-w[x][i], pre[i] = y;

			if(slk[i] < slk[Minloc]) Minloc = i;

		}

		for(int i = 0, inc = slk[Minloc]; i <= n; i++)

			if(vis[i]) dbx[cy[i]] -= inc, dby[i] += inc;

			else slk[i] -= inc;

		y = Minloc;

	}while(~cy[y]);

	while(y) cy[y] = cy[pre[y]], y = pre[y];

}

int KM()

{

	memset(cy, -1, sizeof cy);

	for(int i = 1; i <= n; i++) bfs(i);

	int ret = 0;

	for(int i = 1; i <= n; i++) ret += w[cy[i]][i];

	return ret;

}

int main()

{

	read(n);

	for(int i = 1; i <= n; ++i)

		for(int j = 1; j <= n; ++j)

			read(w[i][j]);

	for(int i = 1, x; i <= n; ++i)

		for(int j = 1; j <= n ; ++j)

			read(x), w[j][i] *= x;

	printf("%d\n", KM());

}

巴特西

KM模板最大权匹配（广搜版） Luogu P1559 运动员最佳匹配问题

最新文章

热门文章

巴特西

KM模板 最大权匹配（广搜版） Luogu P1559 运动员最佳匹配问题

最新文章

热门文章

KM模板最大权匹配（广搜版） Luogu P1559 运动员最佳匹配问题