BZOJ 3275 Number

发布于 2017-05-25  211 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3275

题意:

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


法 1:

网络流还是比较容易想到的... 怎么建模呢,首先想了一个非常萨博的做法... 先对每一个点拆点,拆为入点 x i 和出点 yi   入点与源点连权值 a[i] 的边,出点与汇点连 a[i]... 暴力判断两两点是否互斥,若互斥,则 怒斥 (雾 则入点向出点连个 inf,这样做就是个二分图模型了... 跑最小割即可,需要注意的是 ans 要除个 2....,然而点数扩大了一倍,本来就是 3000... 然而 dinic 玄学的复杂度居然卡过了....

法 2:

标解比较神... 原图本身就是具有二分图的性质的,对于数对 (i,j),若 i,j 均为奇数,则必不满足条件 1,若 i,j 均为偶数,则必有公因数 2,不满足条件 2... 这样原图可以按照奇偶性搞成二分图了... 点数不变,直接最小割,快了 3 倍 qwq

法 1 代码:

法 2 代码:

 


一个非常弱的准退役OIER