• <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
            
            簡明題意:
            將N個物品分成K組,一個字母代表一類,然后給出2種分組方案,求最大相似度
            說白了,這題就是字母的匹配,而權值則為該對匹配對應的字母個數,要求求得一種匹配方案,使得權值和最大。
            解法: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) 評論(0)  編輯 收藏 引用 所屬分類: graph

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

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            国产L精品国产亚洲区久久| 国产99久久久国产精品小说| 中文无码久久精品| 久久夜色精品国产噜噜麻豆| 国产精品一区二区久久| 久久久久久亚洲精品不卡 | 国内精品久久国产大陆| 国产高清国内精品福利99久久| 久久久久亚洲AV成人网人人软件 | 婷婷久久久亚洲欧洲日产国码AV | 成人亚洲欧美久久久久| 久久乐国产综合亚洲精品| 国产91色综合久久免费| 国产精品久久婷婷六月丁香| 久久精品无码一区二区三区| 久久精品99无色码中文字幕| 奇米综合四色77777久久| 久久无码AV中文出轨人妻| 7777久久亚洲中文字幕| 亚洲中文字幕无码久久2020| 久久无码人妻精品一区二区三区| 国产精品无码久久综合 | 人妻少妇精品久久| 精品无码久久久久久尤物| 国产成人精品久久| 亚洲乱码日产精品a级毛片久久 | 久久99热精品| av无码久久久久不卡免费网站| 久久人妻AV中文字幕| 久久综合九色欧美综合狠狠 | 亚洲精品无码久久久影院相关影片| 97久久精品人人做人人爽| 97久久综合精品久久久综合| 亚洲国产精品久久久天堂| 久久久久亚洲av成人无码电影| 久久精品中文字幕有码| 999久久久免费国产精品播放| 色综合久久久久| 久久国产高清一区二区三区| 久久se精品一区精品二区国产| 亚洲成色999久久网站|