hdu 3315 My Brute (二分图最佳匹配,KM算法)

hdu3315 题目链接

题意:两个人分别各有n个怪物。进行n场pk.每只怪物必须恰好进行一场pk.如果先手的第i只怪物赢,会获得v[i]的val,输会减少v[i]的val.给出两个人n只怪物的血量和攻击力。先手的初始战斗顺序为1,2,3..n(后手的战斗顺序一直都是1,2,3..n) 现在问能否通过调整顺序使得先手获得的val最大,如果这个val大于0,表示先手可以赢。如果可以赢,那么还要求调整后的顺序和原始顺序的相似度,并且使得相似度尽可能大(If there are multiple orders, you should choose the one whose order changes the least from the original one)

 

思路:先根据血量和攻击力,n*n的时间处理出每场战斗的输赢信息,然后结合v[i],得到每两个怪物战斗的先手得到的val的值。

然后和hdu 1853类似,依然希望尽可能多的安排不改变。

我们的做法仍然是把w*N,然后钦定的w再+1

然后改变个数,由于存在负数。。。和hdu 1853的处理有区别。。。

想了一下。。。其实用link数组对照初始钦定顺序就好了啊。。。

1A.爽上天。。。

最近各种1A…?好开心。

 

选区_075