KM HDU 3718

  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<string.h>
  4 #include<algorithm>
  5 using namespace std;
  6 
  7 #define MAXN 50
  8 #define inf 65553566
  9 int love[MAXN][MAXN];   /// 记录每个妹子和每个男生的好感度
 10 int ex_girl[MAXN];      /// 每个妹子的期望值
 11 int ex_boy[MAXN];       /// 每个男生的期望值
 12 bool vis_girl[MAXN];    /// 记录每一轮匹配匹配过的女生
 13 bool vis_boy[MAXN];     /// 记录每一轮匹配匹配过的男生
 14 int match[MAXN];        /// 记录每个男生匹配到的妹子 如果没有则为-1
 15 int slack[MAXN];        /// 记录每个汉子如果能被妹子倾心最少还需要多少期望值
 16 
 17 double ans[35];
 18 char s[10010],tmp[10010];
 19 int n,k,m,sum;
 20 
 21 ///为女孩找匹配的男孩
 22 int find(int girl)
 23 {
 24     vis_girl[girl]=1;
 25     for(int boy=0;boy<26;boy++)
 26     {
 27         if(vis_boy[boy]) continue;///如果男孩已经被标记过，则找下一个
 28         int gap=ex_girl[girl]+ex_boy[boy]-love[girl][boy];///看差距
 29         if(gap==0)
 30         {
 31             vis_boy[boy]=1;
 32             if(match[boy]==-1||find(match[boy]))///如果男孩未匹配过或者该男孩的妹子可以找其他人
 33             {
 34                 match[boy]=girl;///将女孩匹配给男
 35                 return 1;
 36             }
 37         }
 38         else
 39         {
 40             slack[boy]=min(slack[boy],gap);
 41         }
 42     }
 43     return 0;
 44 }
 45 int  KM(int n)
 46 {
 47 
 48     memset(match,-1,sizeof(match));
 49     memset(ex_boy,0,sizeof(ex_boy));
 50 
 51     ///每个女生的初始期望值是与他相连的男生最大的好感度
 52     for(int i=0;i<n;i++)
 53     {
 54         ex_girl[i]=love[i][0];
 55         for(int j=1;j<n;j++)
 56         {
 57             ex_girl[i]=max(ex_girl[i],love[i][j]);
 58         }
 59     }
 60     ///尝试为每个女孩匹配男孩
 61     for(int i=0;i<n;i++)
 62     {
 63         fill(slack,slack+n,inf);
 64         while(1)
 65         {
 66 
 67               /// 为每个女生解决归宿问题的方法是 ：如果找不到就降低期望值，直到找到为止
 68               ///记录每轮匹配中南海女孩是否被尝试匹配过
 69             memset(vis_girl,0,sizeof(vis_girl));
 70             memset(vis_boy,0,sizeof(vis_boy));
 71             if(find(i))  break;///如果发现该女孩已经找到归宿，就进行下一个女孩
 72             int d=inf;
 73             for(int j=0;j<n;j++)
 74                 if(!vis_boy[j])///看该男孩如果没有匹配的，就将最小的期望值给他
 75                 d=min(d,slack[j]);
 76 
 77             for(int j=0;j<n;j++)
 78             {
 79                 if(vis_girl[j])///如果女孩已经匹配，则女孩的期望值减去
 80                     ex_girl[j]-=d;
 81                 if(vis_boy[j])
 82                     ex_boy[j]+=d;
 83             }
 84         }
 85     }
 86     int sum=0;
 87     for(int j=0;j<n;j++)
 88         sum+=love[match[j]][j];
 89     return sum;
 90 
 91 }
 92 int main()
 93 {
 94     int t;
 95     int i,j;
 96     char str[5];
 97     scanf("%d",&t);
 98     while(t--)
 99     {
100         scanf("%d%d%d",&n,&k,&m);
101         for(i=0;i<n;i++)
102         {
103             scanf("%s",str);
104             s[i]=str[0];
105         }
106         //s[i]='';
107         for(i=0;i<m;i++)
108         {
109             memset(love,0,sizeof(love));
110             for(j=0;j<n;j++)
111             {
112                 scanf("%s",str);
113                 tmp[j]=str[0];
114             }
115             //tmp[j]='';
116             for(j=0;j<n;j++)
117             {
118                 love[s[j]-'A'][tmp[j]-'A']++;
119             }
120             int res=KM(26);
121             ans[i]=1.0*res/n;
122 
123         }
124            for(i=0;i<m;i++)
125                printf("%.4lf
",ans[i]);
126 
127     }
128 }