题意：
给出一正确字符序列，然后再给出相同长度的字符序列，第二个序列需要确定给定字符与正确序列相对应。求最大相似比率(正确的个数/总个数)。
思路：
很容易直接想到二分图的最大权匹配，将两个相对应的字符建边，并以其重复个数为权值，然后跑一遍KM就可以了。
代码：
#include <algorithm> #include <iostream> #include <string.h> #include <string> #include <cstdio> #include <map> using namespace std; const int maxn = 10005; const int inf = 0x3f3f3f3f; char s[maxn*2]; map<int, int> mp; int T, N, K, M; int num1[maxn], num2[maxn]; int cnt; int weight[30][30]; int match[30]; int lx[30], ly[30]; int visx[30], visy[30]; int slack[30]; int dfs(int cur) { visx[cur] = 1; for(int i = 1; i <= K; ++i) { if(visy[i]) continue; int gap = lx[cur]+ly[i]-weight[cur][i]; if(gap == 0) { visy[i] = 1; if(match[i] == -1 || dfs(match[i])) { match[i] = cur; return 1; } } else slack[i] = min(slack[i], gap); } return 0; } int KM() { memset(match, -1, sizeof match); memset(ly, 0, sizeof ly); for(int i = 1; i <= cnt; ++i) { lx[i] = weight[i][1]; for(int j = 2; j <= K; ++j) lx[i] = max(lx[i], weight[i][j]); } for(int i = 1; i <= cnt; ++i) { memset(slack, 0x3f, sizeof slack); while(1) { memset(visx, 0, sizeof visx); memset(visy, 0, sizeof visy); if(dfs(i)) break; int mins = inf; for(int j = 1; j <= K; ++j) if(!visy[j]) mins = min(mins, slack[j]); for(int j = 1; j <= cnt; ++j) if(visx[j]) lx[j] -= mins; for(int j = 1; j <= K; ++j) if(visy[j]) ly[j] += mins; } } int ans = 0; for(int i = 1; i <= K; ++i) if(match[i] != -1) ans += weight[match[i]][i]; return ans; } int main() { scanf("%d", &T); while(T--) { scanf("%d %d %d", &N, &K, &M); getchar(); gets(s); cnt = 0; mp.clear(); for(int i = 0; i < N; ++i) if(mp.count(s[i*2])) num1[i+1] = mp[s[i*2]]; else { mp[s[i*2]] = ++cnt; num1[i+1] = cnt; } for(int _ = 1; _ <= M; ++_) { memset(weight, 0, sizeof weight); cnt = 0; mp.clear(); gets(s); for(int i = 0; i < N; ++i) if(mp.count(s[i*2])) num2[i+1] = mp[s[i*2]]; else { mp[s[i*2]] = ++cnt; num2[i+1] = cnt; } for(int i = 1; i <= N; ++i) //令cnt为A部个数，防止死循环 ++weight[num2[i]][num1[i]]; printf("%.4f\n", KM()*1.0/N); } } return 0; }
继续加油~
