HDU-2255

题目意思转化之后就是,给你一个二分图(也称
二部图) ,要求选择一些边让左边的点都对应左边的某一个点!该问题也叫做二分图最大匹配。所以可以用KM算法来做这道题。KM前提你要理解匈牙利算法，最大二分匹配问题。

所以先简单阐述一下KM 算法过程：定义连个点集合A，B两个集合定义A与B之间的边为 E

(1) 初始化顶标 lx[] , ly[] 两个数组;

● lx[i]初始化为A集合中 i 点能到B集合某一点的最大权值,

● ly[i]
初始化0;

(2) 用匈牙利找最大匹配;

(3) 如果找到了进行步骤(4);

否则扩边操作,回到步骤(2);

(4) 根据匈牙利算法中的二分图连接,求出最大权值!

注释:为什么要用 lx,ly数组? KM有着贪心的思想,一开始最大匹配时都找每个点的最大权值边,不行再把要求放稍微低一点,再来进行最大匹配!所以,才需要lx,ly数组,以及扩边操作。lx 我们暂且叫做期望权值

KM算法中在匈牙利算法那一部分加了一个条件假设x→y ,则需要 (lx[x]+ly[y])==(value:x→y)

因为一开始lx都是最大权边,ly为0,在进行匈牙利算法之中选择时候,就只会选择指定的边,如果不能够 ,这样做的母的是筛选出边,哪一些对于左图点权值较大的边,这样第一选择一定都是自己点所能到达的最大权值。如果匹配中断了，有点无法匹配，就需要下降要求，就是将
lx 减去某个数（这个数字，是稍微降低已经匹配好的点的期望权值，稍微降低的意思就是：使得减少量尽可能最少）；

如果还是不好理解，推荐这一篇博客；

#include <cstdio>

#include <cstring>

#include <cctype>

#include <cmath>

#include <set>

#include <map>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <string>

#include <vector>

#include <iostream>

#include <algorithm>

#include <stdlib.h>

#include <time.h>

using namespace std;

typedef long long LL;

const int INF=0x3f3f3f3f;

const int MOD=1e9+7;

const int MAXSIZE=1e6+5;

const double eps=0.0000000001;

void fre()

{

    freopen("in.txt","r",stdin);

    freopen("out.txt","w",stdout);

}

#define memst(a,b) memset(a,b,sizeof(a))

#define fr(i,a,n) for(int i=a;i<n;i++)

const int MAXN=305;

int adj[MAXN][MAXN],n;

int lx[MAXN],ly[MAXN],link[MAXN];

bool visx[MAXN],visy[MAXN];

bool dfs(int x) // 匈牙利算法部分

{

	visx[x]=1;

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

	{

		if(adj[x][i]==lx[x]+ly[i]&&visy[i]==0)

		{

			visy[i]=1;

			if(link[i]==-1||dfs(link[i]))

			{

				link[i]=x;

				return true;

			}

		}

	}

	return false;

}

int KM()

{

	memset(link,-1,sizeof(link));

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

	{

		lx[i]=-INF,ly[i]=0;

		for(int j=1;j<=n;j++) lx[i]=max(lx[i],adj[i][j]);

	}

    for(int k=1;k<=n;k++)//匈牙利算法

    {

    	while(1)//对于每个左图的点,进行不断的查找最大权边,一旦发现有

    		// 某一个左图点不能匹配,要求下降一点;继续

    	{

    		memst(visy,0);

    		memst(visx,0);

    		if(dfs(k)) break;

    		int minval=INF;

    		for(int i=1;i<=n;i++) if(visx[i]) for(int j=1;j<=n;j++) if(!visy[j]) minval=min(minval,lx[i]+ly[j]-adj[i][j]);

    		if(minval==INF) return -1;

    		for(int i=1;i<=n;i++) if(visx[i]) lx[i]-=minval;

    		for(int i=1;i<=n;i++) if(visy[i]) ly[i]+=minval;

    	}

    }

    int res=0;

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

    {

    	if(link[i]!=-1) res+=adj[link[i]][i];

    }

    return res;

}

int main()

{

	while(scanf("%d",&n)+1)

	{

		memset(adj,-1,sizeof(adj));

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

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

				scanf("%d",&adj[i][j]);

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

	}

	return 0;

}

/**************************************************/

/**             Copyright Notice                 **/

/**  writer: wurong                              **/

/**  school: nyist                               **/

/**  blog  : http://blog.csdn.net/wr_technology  **/

/**************************************************/

巴特西

HDU-2255(KM算法)

HDU-2255

最新文章

热门文章