• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            The 2010 ACM-ICPC Asia Chengdu Regional Contest - J Similarity 二分圖最佳匹配

            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.

            Similarity

            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(Si == Ti) / L

            L = Length(S) = Length(T), i = 1, 2,... L, where sum(Si == Ti) 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.

            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
            
            簡(jiǎn)明題意:
            將N個(gè)物品分成K組,一個(gè)字母代表一類,然后給出2種分組方案,求最大相似度
            說(shuō)白了,這題就是字母的匹配,而權(quán)值則為該對(duì)匹配對(duì)應(yīng)的字母?jìng)€(gè)數(shù),要求求得一種匹配方案,使得權(quán)值和最大。
            解法:KM
            代碼:
              1# include <stdio.h>
              2# include <string.h>
              3# include <stdbool.h>
              4# define N 201
              5# define max(a,b) ((a)>(b)?(a):(b))
              6# define min(a,b) ((a)<(b)?(a):(b))
              7# define abs(a) ((a)>0?(a):-(a))
              8int map[35][35],ln[N],rn[N],match[N];
              9const int n=26;
             10bool l[N],r[N];
             11int c=0;
             12void init()
             13{
             14  int i,j,p;
             15  memset(match,-1,sizeof(match));
             16  memset(rn,0,sizeof(rn));
             17  for(i=0;i<n;i++)
             18  {
             19     ln[i]=-0xfffffff;
             20     for(j=0;j<n;j++)
             21        ln[i]=max(ln[i],map[i][j]);
             22  }

             23}

             24void adjust()
             25{
             26   int i,j,minnum=0xfffffff,p;
             27   for(i=0;i<n;i++)
             28     if(l[i])
             29     {
             30        for(j=0;j<n;j++)
             31          if(!r[j])
             32             minnum=min(minnum,ln[i]+rn[j]-map[i][j]);
             33     }

             34   for(i=0;i<n;i++)
             35   {
             36     if(l[i])
             37        ln[i]-=minnum;
             38     if(r[i])
             39        rn[i]+=minnum;
             40   }
                   
             41}

             42int dfs(int pos)
             43{
             44    int i;
             45    l[pos]=1;
             46    for(i=0;i<n;i++)
             47    if(!r[i]&&ln[pos]+rn[i]==map[pos][i])
             48    {
             49        r[i]=1;
             50        if(match[i]==-1||dfs(match[i]))
             51        {
             52           match[i]=pos;
             53           return 1;
             54        }

             55    }

             56    return 0;
             57}

             58int main()
             59{
             60    int t;
             61    scanf("%d",&t);
             62    while(t--)
             63    {
             64       int num,k,m,i;
             65       char std[10001],tmp[3];
             66       scanf("%d%d%d",&num,&k,&m);
             67       for(i=0;i<num;i++)
             68       {
             69          scanf("%s",tmp);
             70          std[i]=tmp[0];
             71       }

             72       while(m--)
             73       {
             74         int total=0;
             75         memset(map,0,sizeof(map));
             76         for(i=0;i<num;i++)
             77         {
             78            scanf("%s",tmp);
             79            map[std[i]-'A'][tmp[0]-'A']++;            
             80         }

             81         init();
             82         for(i=0;i<26;i++)
             83         {
             84            while(1)
             85            {
             86               memset(l,0,sizeof(l));
             87               memset(r,0,sizeof(r));
             88               if(dfs(i)) break;
             89               else adjust();
             90            }
               
             91         }

             92         for(i=0;i<26;i++)
             93           total+=map[match[i]][i];
             94         printf("%.4f\n",total/(double)num);
             95       }

             96       
             97    }

             98    return 0;
             99}

            100
            101

            posted on 2010-11-16 00:34 yzhw 閱讀(641) 評(píng)論(0)  編輯 收藏 引用 所屬分類: graph

            <2010年11月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            導(dǎo)航

            統(tǒng)計(jì)

            公告

            統(tǒng)計(jì)系統(tǒng)

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評(píng)論

            閱讀排行榜

            99久久777色| 亚洲精品蜜桃久久久久久| 久久Av无码精品人妻系列| 亚洲国产精品无码久久久蜜芽| 久久香综合精品久久伊人| 秋霞久久国产精品电影院| 色婷婷久久综合中文久久一本| 无码精品久久久天天影视| 7777久久亚洲中文字幕| 亚洲国产精品一区二区三区久久| 亚洲va久久久噜噜噜久久 | 99热热久久这里只有精品68| 午夜精品久久久久9999高清| 亚洲中文久久精品无码ww16 | 亚洲国产天堂久久综合| 日日躁夜夜躁狠狠久久AV| 99久久精品国产一区二区蜜芽| 亚洲精品无码久久久久| 午夜精品久久影院蜜桃| 亚洲国产精品久久久久婷婷软件| 久久精品国产久精国产一老狼| 精品久久久久久无码中文字幕| 少妇精品久久久一区二区三区| 亚洲精品国产综合久久一线| 久久精品国产亚洲av麻豆色欲| 麻豆av久久av盛宴av| 精品久久久久久无码人妻热| 国产精品久久久久天天影视| 亚洲国产另类久久久精品黑人 | 国产精品丝袜久久久久久不卡| 人妻精品久久无码专区精东影业| 99久久这里只精品国产免费| 久久国产成人午夜aⅴ影院 | 国产精品伦理久久久久久| 狠狠色婷婷久久一区二区三区| 亚洲精品乱码久久久久久| 人妻精品久久久久中文字幕| 国产激情久久久久影院老熟女免费| 91视频国产91久久久| 人妻丰满AV无码久久不卡 | 久久99热只有频精品8|