hdu 3718 Similarity (二分图最优匹配,KM算法)

hdu 3718题目链接

题意:东西分类作业,有n个东西,k组,m个学生,不同种类的东西用不同的字母表示,相同种类的用同一个字母表示。不同学生和标准答案之间可能表示同一类东西用的字母不同,但是字母只是一个标号(But the LABEL of group doesn’t make sense and the LABEL is just used to indicate different groups. ) 给出事物分类的标准答案和每个学生的答案现在问每个学生的正确率是多少。

思路:用map<char,int>把字母转化成点的标号。然后初始化权值为0. 对于每个学生,o(n)扫一遍统计出w。然后做一遍KM求最大正确数。从而得到正确率。 因为一个map忘记每次清空,WA了一次。。。2A..

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz