注意读入的时候要用 while判断，如下面的函数
char get()
{
char ch;
while((ch=getchar())<'A' || ch>'Z') ;
return ch;
}
变为一个二分图，用KM算法，时间复杂度O(m*k^3),但可能左边的点数比右边的点数少，即不要求完全匹配；每次边权都初始化为0
/*
* Author: nick wong
* Created Time: 2014年08月28日 星期四 14时01分50秒
* File Name: j.cpp
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
#define out(x) cout<<#x<<": "<<x<<endl
const double eps(1e-8);
const int maxn=31;
const long long maxint=-1u>>1;
const long long maxlong=maxint*maxint;
typedef long long lint;
const int maxp=31;
const int inf=maxint/2;
int w[maxn][maxn],x[maxn],y[maxn];
int prev_x[maxn],prev_y[maxn],son_y[maxn],slack[maxn],par[maxn];
int lx,ly,pop;
int n,k,m;
int mold[310],mnew[310],num_old,num_new;
char _old[10010],_new[10010],tmp[10];
void adjust(int v)
{
son_y[v]=prev_y[v];
if (prev_x[son_y[v]]!=-2)
adjust(prev_x[son_y[v]]);
}
bool find(int v)
{
int i;
for (i=0; i<pop; i++)
if (prev_y[i]==-1)
{
if (slack[i]>x[v]+y[i]-w[v][i])
{
slack[i]=x[v]+y[i]-w[v][i];
par[i]=v;
}
if (x[v]+y[i]==w[v][i])
{
prev_y[i]=v;
if (son_y[i]==-1)
{
adjust(i);
return true;
}
if (prev_x[son_y[i]]!=-1)
continue;
prev_x[son_y[i]]=i;
if (find(son_y[i]))
return true;
}
}
return false;
}
int km()
{
int i,j,m;
for (i=0; i<pop; i++)
{
son_y[i]=-1;
y[i]=0;
}
for (i=0; i<pop; i++)
{
x[i] =0;
for (j = 0; j < pop; j ++)
x[i] = max(x[i],w[i][j]);
}
bool flag;
for ( i=0; i < pop; i ++){
for (j=0;j<pop;j++){
prev_x[j]=prev_y[j]=-1;
slack[j] = inf;
}
prev_x[i] = -2;
if (find(i)) continue;
flag = false;
while (!flag){
m=inf;
for (j=0;j<pop;j++)
if (prev_y[j]==-1)
m=min(m,slack[j]);
for (j=0;j<pop;j++){
if (prev_x[j]!=-1)
x[j]-=m;
if (prev_y[j]!=-1)
y[j]+=m;
else slack[j]-=m;
}
for (j=0;j<pop;j++)
if (prev_y[j]==-1 && !slack[j]){
prev_y[j]=par[j];
if (son_y[j]==-1){
adjust(j);
flag=true;
break;
}
prev_x[son_y[j]]=j;
if (find(son_y[j])){
flag=true;
break;
}
}
}
}
int ans=0;
for(int i=0;i<pop;i++)
ans+=w[son_y[i]][i];
return ans;
}
char get()
{
char ch;
while((ch=getchar())<'A' || ch>'Z') ;
return ch;
}
void init()
{
cin>>n>>k>>m;
num_old=0;
memset(mold,-1,sizeof(mold));
for (int i=1; i<=n; i++)
{
_old[i]=get();
if (mold[_old[i]-'A']==-1) mold[_old[i]-'A']=num_old++;
}
}
void work()
{
while(m--)
{
memset(w,0,sizeof(w));//不可少
memset(mnew,-1,sizeof(mnew));
num_new=0;
for (int i=1; i<=n; i++)
{
_new[i]=get();
if (mnew[_new[i]-'A']==-1) mnew[_new[i]-'A']=num_new++;
w[mnew[_new[i]-'A']][mold[_old[i]-'A']]++;
}
pop=k;
double ans=km();
printf("%.4f\n",ans/n);
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
init();
work();
}
return 0;
}
Description
When we were children, we were always asked to do the classification homework. For example, we were given words {Tiger, Panda, Potato, Dog, Tomato, Pea, Apple, Pear, Orange, Mango} and we were required to classify these words into
three groups. As you know, the correct classification was {Tiger, Panda, Dog}, {Potato, Tomato, Pea} and {Apple, Pear, Orange, Mango}. We can represent this classification with a mapping sequence{A,A,B,A,B,B,C,C,C,C}, and it means Tiger, Panda, Dog belong
to group A, Potato, Tomato, Pea are in the group B, and Apple, Pear, Orange, Mango are in the group C.
But the LABEL of group doesn't make sense and the LABEL is just used to indicate different groups. So the representations {P,P,O,P,O,O,Q,Q,Q,Q} and {E,E,F,E,F,F,W,W,W,W} are equivalent to the original mapping sequence. However, the representations {A,A,A,A,B,B,C,C,C,C}
and
{D,D,D,D,D,D,G,G,G,G} are not equivalent.
three groups. As you know, the correct classification was {Tiger, Panda, Dog}, {Potato, Tomato, Pea} and {Apple, Pear, Orange, Mango}. We can represent this classification with a mapping sequence{A,A,B,A,B,B,C,C,C,C}, and it means Tiger, Panda, Dog belong
to group A, Potato, Tomato, Pea are in the group B, and Apple, Pear, Orange, Mango are in the group C.
But the LABEL of group doesn't make sense and the LABEL is just used to indicate different groups. So the representations {P,P,O,P,O,O,Q,Q,Q,Q} and {E,E,F,E,F,F,W,W,W,W} are equivalent to the original mapping sequence. However, the representations {A,A,A,A,B,B,C,C,C,C}
and
{D,D,D,D,D,D,G,G,G,G} are not equivalent.
The pupils in class submit their mapping sequences and the teacher should read and grade the homework. The teacher grades the homework by calculating the maximum similarity between pupils' mapping sequences and the answer sequence. The definition of similarity
is as follow.
Similarity(S, T) = sum(S i == T i) / L
L = Length(S) = Length(T), i = 1, 2,... L,
where sum(S i == T i) indicates the total number of equal labels in corresponding positions. The maximum similarity means the maximum similarities between S and all equivalent sequences of T, where S is the answer and fixed. Now given
all sequences submitted by pupils and the answer sequence, you should calculate the sequences' maximum similarity.
Input
The input contains multiple test cases. The first line is the total number of cases T (T < 15). The following are T blocks. Each block indicates a case. A case begins with three numbers n (0 < n < 10000), k (0 < k < 27), m (0 < m
< 30), which are the total number of objects, groups, and students in the class. The next line consists of n labels and each label is in the range [A...Z]. You can assume that the number of different labels in the sequence is exactly k. This sequence represents
the answer. The following are m lines, each line contains n labels and each label also is in the range [A...Z]. These m lines represent the m pupils' answer sequences. You can assume that the number of different labels in each sequence doesn't exceed k.
< 30), which are the total number of objects, groups, and students in the class. The next line consists of n labels and each label is in the range [A...Z]. You can assume that the number of different labels in the sequence is exactly k. This sequence represents
the answer. The following are m lines, each line contains n labels and each label also is in the range [A...Z]. These m lines represent the m pupils' answer sequences. You can assume that the number of different labels in each sequence doesn't exceed k.
Output
For each test case, output m lines, each line is a floating number (Round to 4 digits after the decimal point). You should output the m answers in the order of the sequences appearance.
Sample Input
2 10 3 3 A A B A B B C C C C F F E F E E D D D D X X X Y Y Y Y Z Z Z S T R S T R S T R S 3 2 2 A B A C D C F F E
Sample Output
1.0000 0.7000 0.5000 1.0000 0.6667