Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom8月前

12/9
16:46
最小割

[bzoj 3158] 千钧一发

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行一个正整数N。

第二行共包括N个正整数,第 个正整数表示Ai。

第三行共包括N个正整数,第 个正整数表示Bi。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

共一行,包括一个正整数,表示在合法的选择条件下,可以获得的能量值总和的最大值。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

4
3 4 5 12
9 8 30 9

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

39

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

1<=N<=1000,1<=Ai,Bi<=10^6

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

所有奇数都满足条件1 (2a+1)^2+(2b+1)^2=2(2a^2+2a+2b^2+2b+1),只有一个2

所有偶数显然都满足条件2,所以建一个二分图求一遍最小割就可以了

 

[bzoj 3158] 千钧一发