這題看了一會就發現是匹配問題,k個字母跟給出的k個字母間匹配,字母間上下建邊,權值為1
就是求最優匹配了,
#include<stdio.h> #include<string.h> #define N 30 #define inf 0x3fffffff int map[N][N],lx[N],ly[N],sx[N],sy[N],d[N],match[N],n; int find(int x) { int i; sx[x]=1; for(i=0;i<26;i++) { if(sy[i]==1)continue; int temp=lx[x]+ly[i]-map[x][i]; if(temp==0) { sy[i]=1; if(match[i]==-1||find(match[i])==1) { match[i]=x; return 1; } } else d[i]=d[i]>temp?temp:d[i]; } return 0; } int KM() { int i,j,k,min,sum; memset(match,-1,sizeof(match)); memset(ly,0,sizeof(ly)); for(i=0;i<26;i++) { lx[i]=map[i][0]; for(j=1;j<26;j++) if(lx[i]<map[i][j]) lx[i]=map[i][j]; } for(i=0;i<26;i++) { for(j=0;j<26;j++) d[j]=inf; while(1) { memset(sx,0,sizeof(sx)); memset(sy,0,sizeof(sy)); if(find(i)==1)break; min=inf; for(k=0;k<26;k++) if(sy[k]==0&&min>d[k]) min=d[k]; for(j=0;j<26;j++) { if(sx[j]==1)lx[j]-=min; if(sy[j]==1)ly[j]+=min; } } } sum=0; for(i=0;i<26;i++) { sum+=map[match[i]][i]; } return sum; } int main() { int i,j,k,sum,m,t; char ch[3],str[10010]; scanf("%d",&t); while(t--) { scanf("%d%d%d",&k,&n,&m); for(i=0;i<k;i++) { scanf("%s",ch); str[i]=ch[0]; } for(i=1;i<=m;i++) { memset(map,0,sizeof(map)); for(j=0;j<k;j++) { scanf("%s",ch); map[ch[0]-'A'][str[j]-'A']++; } sum=KM(); printf("%.4f\n",1.0*sum/k); } } return 0; }