「BZOJ3275」Number

2014年5月1日4,9095

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

 

avatar
1 Comment threads
4 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
4 Comment authors
hzwer我是蒟蒻Mektpoyhjz Recent comment authors
  Subscribe  
提醒
hjz

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

Mektpoy

。。。