[文章目录]
Description
有N个正整数，需要从中选出一些数，使这些数的和最大。若两个数a,b同时满足以下条件，则a,b不能同时被选。n<=3000
1:存在正整数C，使a*a+b*b=c*c
2:gcd(a,b)=1
求一个图的最大点独立集是个不可解问题。发现奇数和奇数的平方和只能含有一个2，不满足第一个条件。而偶数和偶数不满足第二个条件。
那么问题就变成求一个二分图的最大点独立集，网络流【更改s和t连向点的流量】即可。
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,a[3100],b[3100],s,t,ans;
int head[3100],to[4501000],nxt[4501000],f[4501000],cnt=1;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
int dis[3100];
queue<int>q;
int gcd(int x,int y){return !y?x:gcd(y,x%y);}
bool bfs()
{
memset(dis,-1,sizeof dis);
while(!q.empty()) q.pop();
q.push(s); dis[s]=0; int x;
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==-1)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(f[i],tmp));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) return flow;
}
return flow-tmp;
}
int main()
{
scanf("%d",&n); s=n+1; t=s+1;
int x;
for(int i=1;i<=n;++i)
{
scanf("%d",&x);
ans+=x;
if(x&1) a[++a[0]]=x;
else b[++b[0]]=x;
}
int c,tmp;
for(int i=1;i<=a[0];++i)
for(int j=1;j<=b[0];++j)
{
if(gcd(a[i],b[j])!=1) continue;
c=a[i]*a[i]+b[j]*b[j];
tmp=(int)sqrt(c);
if(tmp*tmp==c||(tmp+1)*(tmp+1)==c||(tmp-1)*(tmp-1)==c) add(i,j+a[0],inf);
}
for(int i=1;i<=a[0];++i) add(s,i,a[i]);
for(int i=1;i<=b[0];++i) add(a[0]+i,t,b[i]);
while(bfs()) ans-=dinic(s,inf);
printf("%d",ans);
return 0;
}