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

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

@krydom8月前

10/15
10:24
最小割

[bzoj 3275] Number

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

 有N个正整数,需要从中选出一些数,使这些数的和最大。
若两个数a,b同时满足以下条件,则a,b不能同时被选
1:存在正整数C,使a*a+b*b=c*c
2:gcd(a,b)=1

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

第一行一个正整数n,表示数的个数。
第二行n个正整数a1,a2,?an。

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

最大的和。

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

5
3 4 5 6 7

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

22

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

n<=3000。

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

最小割,将不能同时选的两个点连一条权值为inf的边,表示两边至少有一条边被割掉

c++:

pascal:

 

[bzoj 3275] Number