当前位置: 代码迷 >> 综合 >> HDU 2255 奔小康赚大钱 (二分图:KM算法)
  详细解决方案

HDU 2255 奔小康赚大钱 (二分图:KM算法)

热度:46   发布时间:2024-01-16 13:42:23.0

题意:

中文题不解释

要点:

KM算法是求完备匹配下的最大权匹配: 在一个二分图内,左顶点为X,右顶点为Y,现对于每组左右连接X[i]Y[j]有权w[i][j],求一种匹配使得所有w[i][j]的和最大。注意完备匹配定义:|X|=|Y|=匹配数。这算法还是比较难的,证明我还是半懂不懂的,具体流程还是可以的。基本上就是利用增广路,不断修改点标,找可行边什么的。

参考博客:点击打开链接

这题就是个裸题,不过我一开始一直TLE,换了复杂度为O(N^3)的还是很多问题,后来发现模板都看错了。真挺难的这算法,什么时候证明一下,感觉没完全搞懂。


17132269 2016-05-12 15:41:17 Accepted 2255 780MS 2108K 2008 B C++ seasonal
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 310;
const int inf = 0x3f3f3f3f;int visx[N], visy[N];
int lx[N], ly[N], w[N][N];
int slack[N],girl[N];
int nx,ny;int find(int x)
{visx[x] = 1;for (int y = 1; y <= ny; y++){if (visy[y])continue;int t = lx[x] + ly[y] - w[x][y];if (t==0){visy[y] = 1;if (girl[y] == -1 || find(girl[y])){girl[y] = x;return 1;}		}else if (slack[y] > t)//如果不在相等子图中就取最小的slack[y] = t;	}return 0;
}int km()
{int i,j;memset(ly, 0, sizeof(ly));memset(girl, -1, sizeof(girl));for (i = 1; i <= nx; i++){lx[i] = -inf;for (j = 1; j <= ny; j++)if (lx[i] < w[i][j])lx[i] = w[i][j];//lx先取连接中权值最大的}for (i = 1; i <= nx; i++){for (j = 1; j <= ny; j++)slack[j] = inf;while (1){memset(visx, 0, sizeof(visx));memset(visy, 0, sizeof(visy));if (find(i))				//如果成功说明增广成功,进入下一个点的增广break;					//若失败(没有找到增广轨),则需要改变一些点的标号,使得图中可行边的数量增加。        int d = inf;				for (j = 1; j <= ny; j++)	if (!visy[j] && d>slack[j])d = slack[j];		//取没有遍历到的Y点的(也就是连接但是相加不为权值)的slack中的最小值作为dfor (j = 1; j <= nx; j++)if (visx[j])lx[j] -= d;			//将所有在增广轨中(就是在增广过程中遍历到)的X方点的标号全部减去一个常数d,for (j = 1; j <= ny; j++)if (visy[j])ly[j] += d;			//所有在增广轨中的Y方点的标号全部加上一个常数delseslack[j] -= d;		//不在交错树中的Y对应的slack也要-d}}int sum = 0;for (i = 1; i <= ny; i++)if (girl[i] != -1)sum += w[girl[i]][i];return sum;
}int main()
{int i,j,n;while (~scanf("%d", &n)){nx = ny = n;for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)scanf("%d", &w[i][j]);int ans = km();printf("%d\n", ans);}return 0;
}