【bzoj3275】Number

2014年5月1日1,8575

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。

题解

将所有点拆成2个

0向i连权为a[i]的边,a[i]向T连权为a[i]的边

有关系的点互相连边,权为inf

答案是tot-ans/2

 

  • hjz2014年5月21日 下午6:30 回复

    题解认真点写行不——看看人家云神写的
    将数分为两部分,
    若a 为奇数,则从源连一条容量为a 边到i;
    若a 为偶数,则从i连一条容量为a 的边到汇;
    若a ,a 互斥,则从奇数点连一条容量为无穷大的边到偶数点,
    然后做最大流,a 的和减去最大流既是答案。

    #1  
    • hzwer2014年5月21日 下午7:06 回复
      admin

      啊我似乎没分奇偶啊。。

      #11
      • 我是蒟蒻2014年5月25日 上午10:12 回复

        那个……不分奇偶也是可以的,但是似乎可以证明奇数和奇数,偶数和偶数之间似乎是不行的……然后就可以少一半的点

        #12
    • Mektpoy2014年5月23日 下午6:45 回复

      。。。

      #11