491 C 二分图最佳匹配

Published On March 25, 2015

告诉你字符串长度 n 和字符串中字母种类数 k （从a开始依次数k个），给你两串相同长度的字符串，要求你找到一种 k种到 k种的一一对应变换关系，使变换后的字符串a，与字符串b的相同字母数最多，输出最多的相同字母数和这种方案下的对应变换关系。

思路：两个字符串长度相同，从0到n-1遍历长度，然后将 g[a[i]][b[i]]++;构造邻接矩阵。进行二分图匹配即可。

Reference 1

Reference 2

拓展阅读

注意点：

条件是加权完全二分图，左右节点数必须相同。权W(xj yj)≥0。
初始化的时候左节点点标l[i]全为与 i 相连的边的最大权值，右节点点标 r[j] 全为0
调用一次path的复杂度是O(n)
solve()中第一层for循环的意义是保证每个点都在匹配方案中。进入循环后，如果path()为真，就break，不然就修改l[i] 和 r[j] 加入一些点和边。
一开始所有的左节点都在图中，而右节点不全在图中，在加边的过程中，所有右节点渐渐加入到图中。
其实整个过程是一个不断寻边的过程。因为在整个过程中都保持 l(x)+l(y)>=w(xy) 这个条件，所以“相等子图”中的完备匹配必然比其他匹配方式更优。

这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。

/**
 * 
 * @authors ZhuFengdaaa (ZhuFengdaaa@gmail.com)
 * @date    2015-03-24 12:32:13
 */

 #include<iostream>
 #include<cstdio>
 #include<vector>
 #include<algorithm>
 #include<cstring>
 #include<cmath>
 using namespace std;

int n,k;
const int INF = 1<<30;
const int V = 52;
char str1[2000000],str2[2000000];
int g[V][V];
bool usex[V],usey[V];
int match[V],lx[V],ly[V];
int slack[V];
void init()
{
	//初始化松弛
	for (int i = 0; i < k; ++i)
	{
		slack[i]=INF;
	}
	//初始化匹配 match[j(左边节点序号)]=i(右边节点序号)
	memset(match,-1,sizeof(match));
	//初始化点标
	for (int i = 0; i < k; ++i)
	{
		lx[i]=0;
		ly[i]=0;
		for (int j = 0; j < k; ++j)
		{
			if(lx[i]<g[i][j])
				lx[i]=g[i][j];
		}
		
	}
}

/* 调用一次path的复杂度是O(n) */
bool path(int u)
{
	usex[u]=1;
	for (int v = 0; v < k; ++v)
	{
		//不在相等子图中，修改松弛函数slack[]
		if(lx[u]+ly[v]-g[u][v]>0)
		{
			slack[v]=min(slack[v],lx[u]+ly[v]-g[u][v]);
		}
		if(!usey[v]&&(lx[u]+ly[v]-g[u][v]==0)){
			usey[v]=1;
			if(match[v]==-1||path(match[v]))
			{
				match[v]=u;
				return true;
			}
		}
	}
	return false;
}
void solve()
{
	init();
	// 从0到k-1遍历是为了保证每个点都被完全匹配
	for (int i = 0; i < k; ++i)
	{
		//修改点标直到出现完全匹配为止
		while(1)
		{
			memset(usex,0,sizeof(usex));
			memset(usey,0,sizeof(usey));
			if(path(i))break;
			int d= INF;
			for (int i = 0; i < k; ++i)
			{
				d=min(d,slack[i]);
			}
			for (int i = 0; i < k; ++i)
			{
				if(usex[i])
					lx[i]-=d;
				if(usey[i])
					ly[i]+=d;
			}
		}
	}
	int res=0;
	for (int i = 0; i < k; ++i)
	{
		res+=g[match[i]][i];
	}
	printf("%d\n", res);
	int pt[52];
	for (int i = 0; i < k; ++i)
	{
		pt[match[i]]=i;
	}
	for (int i = 0; i < k; ++i)
	{
		printf("%c", pt[i]>=26?pt[i]-26+'A':pt[i]+'a');
	}
	printf("\n");
}
int main()
{
	while(cin>>n>>k)
	{
		memset(g,0,sizeof(g));
		cin>>str1>>str2;
		for (int i = 0; i < n; ++i)
		{
			int a,b;
			if('a'<=str1[i]&&str1[i]<='z'){
				a=str1[i]-'a';
			}
			else{
				a=str1[i]-'A'+26;
			}
			if('a'<=str2[i]&&str2[i]<='z'){
				b=str2[i]-'a';
			}
			else{
				b=str2[i]-'A'+26;
			}
			g[a][b]++;
		}
		solve();
	}
}

Tags: CodeForce Algorithm

491 C 二分图最佳匹配

Comments: