链接:http://acm.hdu.edu.cn/showproblem.php?pid=3718
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.
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.
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
Author
LIN, Yue
Source
Recommend
zhouzeyong
题目很明显,就是利用KM算法。。这个很早就想到过了。
但是一直没有动手敲过这个题目。
今天鼓起勇气敲了下。。还是发现了不少问题。
首先是k和m输入反了,找了好久都不知道是哪儿WA了。。
然后就是建图,建图可以用26个顶点来建图。
其它的建图方式可能回超时。
我的代码:
分享到:
相关推荐
收集的部分HDOJ杭电ACM题的代码 大牛勿下 全是基础供初级acmer使用
自己积累的部分杭电oj的(hdu)解题代码。。大家有空来看看。 基本上是自己写的哈。有错误之处请指教、
杭电oj4405,一道简单的概率dp题目
杭电acm解题报告 详细解析2000-2099 适合acm初学者
ACM ICPC HDOJ1000
(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数
ACM/ICPC 2010年多校联合第十场第九题的解题报告及代码,AC代码有三个,最好的是src
此程序为hdu的acm2010题,就是解决水仙花数问题
杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用
杭州电子科技大学hdoj1002,大整数相加问题
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
hdoj的一些题目分类,由hdu大牛搜集,希望对做ac的同志们有帮助
HDU1059的代码
杭电ACMhdu1163
HDU ACM 2005第几天 C++ http://acm.hdu.edu.cn/listproblem.php?vol=11 2005题 第几天?
ACM ICPC HDOJ 1005
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规