hdu 2255（二分圖的最佳完美比對+KM算法）

hdu 2255

思路：

KM模闆題。

二分圖的最大完美比對：有一個二分圖，每條邊有一個權值，求出權值最大的完美比對。

KM模闆與詳解

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 550;
const int INF = 99999999;
int love[maxn][maxn],n;
int vis_g[maxn],vis_b[maxn]; //分别對男，女的标記 
int ex_b[maxn],ex_g[maxn]; //對男女的期望值 
int sk[maxn],link[maxn]; //sk表示男生得到女生的芳心所需的最小期望值,link表示每個男生所配對的女生 
int MIN(int x,int y){
	return x<y?x:y;
}
int MAX(int x,int y){
	return x>y?x:y;
}
bool dfs(int u){ //尋找女生所期望的對象 
	int i,j;
	vis_g[u] = 1;
	for(i=0;i<n;i++){
		if(vis_b[i]) continue;
		int gap = ex_g[u]+ex_b[i]-love[u][i];
		if(gap==0){ //符合要求 
			vis_b[i] = 1;
			if(link[i]==-1||dfs(link[i])){
				link[i] = u;
				return true;
			}
		}
		else sk[i] = MIN(sk[i],gap); //更新男生要得到女生芳心所需的最小值 
	}
	return false;
}
int KM(){
	int i,j;
	fill(link,link+maxn,-1); //每個男生都沒有配對 
	memset(ex_b,0,sizeof(ex_b)); //每個男生初始的期望值為0 
	for(i=0;i<n;i++){
		for(ex_g[i]=love[i][0],j=1;j<n;j++) ex_g[i] = MAX(ex_g[i],love[i][j]); //女生初始的期望值是所有與她相連的男生中最帥的 
	}
	for(i=0;i<n;i++){
		fill(sk,sk+maxn,INF); //一開始女生對男生地期望值為INF，假設所有男生都得不到女生的青睐 
		while(1){
			memset(vis_b,0,sizeof(vis_b));
			memset(vis_g,0,sizeof(vis_g));
			if(dfs(i)) break; //如果女生找到合适的男生 
			int d = INF;
			for(j=0;j<n;j++)
			if(!vis_b[j]) d = MIN(d,sk[j]); //這個女生要找到合适男生所需要降低的最小标準 
			for(j=0;j<n;j++){
				if(vis_g[j]) ex_g[j] -= d; //女生的期望值下降d，以便于找到合适的男生。 
				if(vis_b[j]) ex_b[j] += d; //這個男生得到多個女生的青睐，男生地期望值上升 
				else sk[j] -= d; //男生所需要得到女生芳心的最小期望降低d 
			}
		}
	}
	int ans = 0;
	for(i=0;i<n;i++) ans += love[link[i]][i];//求出第i個男生和他的女票的期望值。 
	return ans;
}
int main(void)
{
	int i,j;
	while(~scanf("%d",&n)){
		for(i=0;i<n;i++)
			for(j=0;j<n;j++) scanf("%d",&love[i][j]); //輸入每個女生對每個男生的期望值 
		printf("%d\n",KM());
	}
	return 0;
}