HDU 2813 One fihgt one（KM算法解决最小权值匹配）

InputMultiple cases. For each case ,there are three integers in the first line , namely n,m (1<=n<=m<=200)and k (n<=k<=m*n). 
The next k lines are the information about k possible fights , for each line are two strings (no more than 20 characters ) and an integer. The first string indicates Lv Bu’s general and the second , of course , Cao Cao’s , and the integer is the injury Lv Bu’s general would get if this fight were chosen. OutputOne integer , the least injuries Lv Bu’s generals would get. Sample Input

2 3 5
LvBu ZhangFei 6
LvBu GuanYu 5
LvBu XuChu 4
ZhangLiao ZhangFei 8
ZhangLiao XuChu 3

Sample Output

8

题目意思说吕布和曹操两军对垒，现在派将军就叫阵。吕布一方有N个将军，曹操一方有M个将军。然后有K个关系，每个关系由3元描述，吕布一方的将军名字，曹操一方的将军名字，如果两者对战将会损失X点血量。

现在问吕布一方在尽可能出战的情况下（别人来叫阵不能不出）损失的最小血量。

那么这个就有点像二分图匹配了，而且是带边权的二分图匹配。

左边是吕布的将军，右边是曹操的将军。现在要损失的血量最小，那么就找边权最小的将军对战（挑软柿子捏）

求二分图最大边权匹配我们有KM算法，现在使求二分图最小边权匹配。

其实只需要在KM算法上改一点就可以。把每条边的边权改为负值。

这样求出来的答案就是负值，且是所有可能中负值最大一个。

在去负值，那就是最小了，此时答案就是所有可能中最小的一个。也就是最小边权匹配。

有一道类似的题目，大家可以也可以看看点我传送 (๑ •̀ㅂ•́) ✧

#include<iostream>
#include<cstdio>
#include<cstring>
#include<functional>
#include<algorithm>
#include<map>
#define maxn 240
#define inf 0x3f3f3f3f
using namespace std;
int n,m,k;
map<string,int>mapsx,mapsy;
int link[maxn][maxn];
int match[maxn];
int slack[maxn];
bool visx[maxn],visy[maxn];
int ex[maxn],ey[maxn];
bool dfs(int x)
{
	visx[x]=1;
	for(int y=1;y<=m;y++)
	{
		if(visy[y])
			continue;
		int gap=ex[x]+ey[y]-link[x][y];
		if(gap==0)
		{
			visy[y]=1;
			if(match[y]==0||dfs(match[y]))
			{
				match[y]=x;
				return 1;
			}
		}
		else
			slack[y]=min(slack[y],gap);
	}
	return 0;
}

int KM()
{
	int i,j;
	memset(ex,0,sizeof(ex));
	memset(ey,0,sizeof(ey));
	memset(match,0,sizeof(match));
	for(i=1;i<=n;i++)
	{
		ex[i]=link[i][1];
		for(j=2;j<=m;j++)
			ex[i]=max(ex[i],link[i][j]);
	}
	for(i=1;i<=n;i++)
	{
		memset(slack,0x3f,sizeof slack);//fill(slack,slack+m+1,inf);
		while(1)
		{
			memset(visx,0,sizeof(visx));
			memset(visy,0,sizeof(visy));
			if(dfs(i))
				break;
			else
			{
			int d=inf;
			for(j=1;j<=m;j++)
				if(!visy[j])
					d=min(d,slack[j]);
			for(j=1;j<=n;j++)
				if(visx[j])
					ex[j]-=d;
			for(j=1;j<=m;j++)
				if(visy[j])
					ey[j]+=d;
				else
					slack[j]-=d;
			}
		}
	}
	int sum=0;
	for(i=1;i<=m;i++)
		sum+=link[match[i]][i];
	return sum;
}

int main()
{
	int i,j,cntx,cnty,c;
	int ans;
	char a[30],b[30];
	while(scanf("%d%d%d",&n,&m,&k)!=EOF)
	{
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
				link[i][j]=-inf;//初始化地图，应该初始化为-inf
		}//开始初始化为0错了好久
		cntx=cnty=1;
		for(i=1;i<=k;i++)
		{
			scanf("%s%s%d",&a,&b,&c);
			if(mapsx.find(a)==mapsx.end())//把人名映射
				mapsx[a]=cntx++;
			if(mapsy.find(b)==mapsy.end())
				mapsy[b]=cnty++;
			link[mapsx[a]][mapsy[b]]=-c;
		}
		ans=KM();//二分图最大权值匹配
		printf("%d\n",-ans);
	}
}