HDU3718ZOJ3425 Similarity（The 2010 ACM-ICPC Asia Chengdu Regional Contest，加权二分图的最优匹配）

简单说就是求出两个字符串的相似程度。
题目意思说的是学生得到一个任务，把不同物品分类，比如苹果，香蕉属于水果等，
为了方便，给每个类别用字母编号。就得到题目中的字符串。每个学生的分类标准不一样，所以有不用的答案。现在问有多少个是正确的。最后结果是正确的答案除以总数。
比如第一个样例，ABC 和DEF的，如果把A换成F，B换成E，C换成D，那么就是一模一样的了。所以相似度是1；


解释一下输入数据，首先输入测试样例组数，每组开始包含3个数字，第一个数字代表有多少个物品，也就是每个字符串中有多少个字符。第二个数字代表每个字符串中有多少种字符。第三个数字表示有多少个学生需要比对。


解题思路：先从暴力的方面想，枚举每种匹配情况，找出最大匹配结果。那就是答案。
思路是这样，但这样做肯定会超时。所以需要优化。
第一个优化就是枚举匹配的情况的时候，优先选择当个字符匹配多的情况，在匹配第二多的情况。
但是这样枚举情况很复杂，前面的选择会对后面的选择造成影响。
这道题目用如果用到二分图加权匹配，就比较好解决。
首先是建图过程，把需要匹配的两个字符串划分为二分图。接下来构建二分图的边。
从左到右，统计每个字符对应位置。这样就统计了每种匹配情况。
然后就进行二分图加权匹配。
二分图加权匹配的过程就是每次优先选择权值大的边，如果后面有冲突，在调整，选择权值次之的边，以此类推下去，最后到没办法选了位置


建图方式，按位比较，一遍过，统计出每个字符串匹配的情况。

在KM里面循环的时候，26个字母都循环一遍

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define n 60
#define maxn 10010
#define inf 0x3f3f3f3f
using namespace std;
int num,spe,group;
char str[maxn],str1[maxn];
int visx[n],visy[n],slack[n];
int lx[n],ly[n],match[n],edge[n][n];
int nx,ny;
int dfs(int v)
{
	visx[v]=1;
	for(int i=0;i<ny;i++)
	{
		if(visy[i])
			continue;
		if(lx[v]+ly[i]==edge[v][i])
		{
			visy[i]=1;
			if(match[i]==-1||dfs(match[i]))
			{
				match[i]=v;
				return 1;
			}
		}
		else
			slack[i]=min(slack[i],lx[v]+ly[i]-edge[v][i]);
	}
	return 0;
}
void km()
{
	memset(match,-1,sizeof(match));
	memset(lx,0,sizeof(lx));
	memset(ly,0,sizeof(ly));
	for(int i=0;i<nx;i++)
		for(int j=0;j<ny;j++)
			lx[i]=max(lx[i],edge[i][j]);
	for(int i=0;i<nx;i++)
	{
		memset(slack,0x3f,sizeof(slack));
		while(1)
		{
			memset(visx,0,sizeof(visx));
			memset(visy,0,sizeof(visy));
			if(dfs(i))
				break;
			else
			{
				int d=inf;
				for(int j=0;j<ny;j++)
					if(!visy[j])
						d=min(d,slack[j]);
				for(int j=0;j<nx;j++)
					if(visx[j])
						lx[j]-=d;
				for(int j=0;j<ny;j++)
					if(visy[j])
						ly[j]+=d;
					else
						slack[j]-=d;
			}
		}
	}
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d",&num,&spe,&group);
		for(int i=0;i<num;i++)
			scanf(" %c",&str[i]);
		while(group--)
		{
			for(int i=0;i<num;i++)
				scanf(" %c",&str1[i]);
			memset(edge,0,sizeof(edge));
			for(int i=0;i<num;i++)
				edge[str[i]-'A'][str1[i]-'A']++;//和别人写的调换，不影响结果
			nx=26; ny=26;
			km();
			int ans=0;
			for(int i=0;i<ny;i++)
				ans+=edge[match[i]][i];
			printf("%.4lf\n",1.0*ans/num);
		}
	}

}