hdu 3722 Card Game (有向环覆盖,拆点,二分图最佳匹配,KM算法)

hdu 3722题目链接

题意:n个串,a串放在b串前面的val值是“The score of sticking two cards is the longest common prefix of the second card and the reverse of the first card”.问如何放使得总的val最大。

思路:先暴力处理出每两个的权值。。200*200*1000的复杂度。。还是可以接受的。。

然后把每个串看成了一个点,由于一个串最多可以被放在前面一次,被放在后面一次,所以可以类比图论中的环的入度和出度为1.

然后跑一遍KM. 1A,开心。

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz