题解：
KM算法
把每一个点拆成n个
然后改变编圈
代码：
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; const int N=105; char s[5],q[N][5]; int cnt,a[N][N],z,e,cas,b[N*N]; int visr[N],T,x,y,exl[N],exr[N],visl[N],match[N],slack[N],n,m; int in(char s[]) { for (int i=1;i<=cnt;i++) if (q[i][0]==s[0])return i; q[++cnt][0]=s[0]; return cnt; } int dfs(int x) { visl[x]=1; for (int i=1;i<=m;i++) if (!visr[i]) { int k=exl[x]+exr[i]-a[x][i]; if (k==0) { visr[i]=1; if (!match[i]||dfs(match[i])) { match[i]=x; return 1; } } else slack[i]=min(slack[i],k); } return 0; } int km() { memset(exl,0,sizeof exl); memset(exr,0,sizeof exr); for (int i=1;i<=m;i++) for (int j=1;j<=m;j++)exl[i]=max(exl[i],a[i][j]); memset(match,0,sizeof match); for (int i=1;i<=m;i++) { memset(slack,0x3f,sizeof slack); while (1) { memset(visl,0,sizeof visl); memset(visr,0,sizeof visr); if (dfs(i))break; int d=1e9; for (int j=1;j<=m;j++) if (!visr[j])d=min(d,slack[j]); for (int j=1;j<=m;j++) if (visl[j])exl[j]-=d; for (int j=1;j<=m;j++) if (visr[j])exr[j]+=d; else slack[j]-=d; } } int ans=0,flag=0; for (int i=1;i<=m;i++)ans+=a[match[i]][i]; return ans; } int main() { scanf("%d",&T); while (T--) { scanf("%d%d%d",&n,&m,&e); cnt=0; memset(q,0,sizeof q); for (int i=1;i<=n;i++) { scanf("%s",s); b[i]=in(s); } while (e--) { cnt=0; memset(q,0,sizeof q); memset(a,0,sizeof a); for (int i=1;i<=n;i++) { scanf("%s",s); a[b[i]][in(s)]++; } printf("%.4lf ",(double)km()/n); } } }