hdu 3718

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3718

思路：题目求的是两字符串的最大相似度
思路：因为第一个串的一种字母只能匹配第二个串的一种字母，所以可以转化为求
【字母的最大匹配值/n】
建图：【例】

View Code

 1 #include<iostream>
 2 #include<string>
 3 const int MAXN=30;
 4 const int inf=1<<30;
 5 using namespace std;
 6 int match[MAXN];
 7 int lx[MAXN],ly[MAXN];
 8 int map[MAXN][MAXN];
 9 bool visitx[MAXN],visity[MAXN];
10 
11 int Hungary(int u){
12     visitx[u]=true;
13     for(int i=1;i<MAXN;i++){
14         if(!visity[i]&&lx[u]+ly[i]==map[u][i]){
15             visity[i]=true;
16             if(match[i]==-1||Hungary(match[i])){
17                 match[i]=u;
18                 return true;
19             }
20         }
21     }
22     return false;
23 }
24 
25 void KM_prefect_match(){
26     int tmp;
27     memset(lx,0,sizeof(lx));
28     memset(ly,0,sizeof(ly));
29     for(int i=1;i<MAXN;i++){
30         for(int j=1;j<MAXN;j++){
31             lx[i]=max(lx[i],map[i][j]);
32         }
33     }
34     for(int i=1;i<MAXN;i++)
35     {
36         while(1){
37             memset(visitx,false,sizeof(visitx));
38             memset(visity,false,sizeof(visity));
39             if(Hungary(i))
40                 break;
41             else {
42                 tmp=inf;
43                 for(int j=1;j<MAXN;j++)if(visitx[j]){
44                     for(int k=1;k<MAXN;k++){
45                         if(!visity[k]&&tmp>lx[j]+ly[k]-map[j][k]){
46                             tmp=lx[j]+ly[k]-map[j][k];
47                         }
48                     }
49                 }
50                 for(int j=1;j<MAXN;j++){
51                     if(visitx[j])
52                         lx[j]-=tmp;
53                     if(visity[j])
54                         ly[j]+=tmp;
55                 }
56             }
57         }
58     }
59 }
60 
61 
62 int main(){
63     int _case;
64     scanf("%d",&_case);
65     while(_case--){
66         int n,k,m;
67         scanf("%d%d%d",&n,&k,&m);
68         char str[4];
69         string s;
70         for(int i=1;i<=n;i++){
71             scanf("%s",str);
72             s+=str[0];
73         }
74         for(int i=1;i<=m;i++){
75             memset(match,-1,sizeof(match));
76             memset(map,0,sizeof(map));
77             for(int j=0;j<n;j++){
78                 scanf("%s",str);
79                 map[s[j]-'A'+1][str[0]-'A'+1]++;
80             }
81             KM_prefect_match();
82             int ans=0;
83             for(int j=1;j<MAXN;j++){
84                 if(match[j]!=-1){
85                     ans+=map[match[j]][j];
86                 }
87             }
88             printf("%.4lf\n",ans*1.0/n);
89         }
90     }
91     return 0;
92 }