3275: Number
题目：传送门
题解：
双倍经验@bzoj3158
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define qread(x) x=read()
using namespace std;
const int inf=;
int n,st,ed,sum;
int A[],B[];
struct node
{
int x,y,c,next,other;
}a[];int len,last[];
void ins(int x,int y,int c)
{
int k1,k2;
k1=++len;
a[len].x=x;a[len].y=y;a[len].c=c;
a[len].next=last[x];last[x]=len; k2=++len;
a[len].x=y;a[len].y=x;a[len].c=;
a[len].next=last[y];last[y]=len; a[k1].other=k2;
a[k2].other=k1;
}
int list[],h[],head,tail;
bool bt_h()
{
memset(h,,sizeof(h));h[st]=;
list[]=st;head=;tail=;
while(head!=tail)
{
int x=list[head];
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(h[y]== && a[k].c>)
{
h[y]=h[x]+;
list[tail++]=y;
}
}
head++;
}
if(h[ed]>)return true;
return false;
}
int find_flow(int x,int flow)
{
if(x==ed)return flow;
int s=,t;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(h[y]==h[x]+ && a[k].c> && flow>s)
{
s+=t=find_flow(y,min(a[k].c,flow-s));
a[k].c-=t;a[a[k].other].c+=t;
}
}
if(s==)h[x]=;
return s;
}
int gcd(int x,int y) {if(x>y)swap(x,y);if(x==)return y;return gcd(y%x,x);}
bool pd(int x,int y)
{
int t=int(sqrt(double(x*x+y*y)));
if(t*t!=x*x+y*y)return true;
if(gcd(x,y)>)return true;
return false;
}
int main()
{
freopen("number.in","r",stdin);
freopen("number.out","w",stdout);
sum=;
scanf("%d",&n);
len=;memset(last,,sizeof(last));
for(int i=;i<=n;i++){scanf("%d",&B[i]);sum+=B[i];}
st=n+;ed=st+;
for(int i=;i<=n;i++)
{
if(B[i]%==)ins(st,i,B[i]);
else ins(i,ed,B[i]);
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)if(i!=j)
if((B[i]%==) && (B[j]%==) && pd(B[i],B[j])==false)
ins(i,j,);
int ans=;
while(bt_h())ans+=find_flow(st,);
printf("%d\n",sum-ans);
return ;
}