有N個正整數,需要從中選出一些數,使這些數的和最大。
若兩個數a,b同時滿足以下條件,則a,b不能同時被選
1:存在正整數C,使a*a+b*b=c*c
2:gcd(a,b)=1
n<=3000。
網絡流
我們可以發現只有a和b奇偶性不同時才能滿足題目條件。
然後對於所有奇數連邊(s,i,a[i]),對於所有偶數連邊(i,t,a[i]),對於滿足題意的奇數i和偶數j連邊(i,j,inf)。
最後跑一次最小割,從總和中減去最小割即為答案。
#include#include #include #include #include #include #include #define F(i,j,n) for(int i=j;i<=n;i++) #define D(i,j,n) for(int i=j;i>=n;i--) #define ll long long #define pa pair #define maxn 3100 #define maxm 10000000 #define inf 1000000000 using namespace std; struct edge_type { int next,to,v; }e[maxm]; int head[maxn],cur[maxn],dis[maxn],a[maxn]; int n,s,t,ans=0,tot=0,cnt=1; inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void add_edge(int x,int y,int v) { e[++cnt]=(edge_type){head[x],y,v};head[x]=cnt; e[++cnt]=(edge_type){head[y],x,0};head[y]=cnt; } inline bool bfs() { queue q; memset(dis,-1,sizeof(dis)); dis[s]=0;q.push(s); while (!q.empty()) { int tmp=q.front();q.pop(); if (tmp==t) return true; for(int i=head[tmp];i;i=e[i].next) if (e[i].v&&dis[e[i].to]==-1) { dis[e[i].to]=dis[tmp]+1; q.push(e[i].to); } } return false; } inline int dfs(int x,int f) { if (x==t) return f; int tmp,sum=0; for(int &i=cur[x];i;i=e[i].next) { int y=e[i].to; if (e[i].v&&dis[y]==dis[x]+1) { tmp=dfs(y,min(f-sum,e[i].v)); e[i].v-=tmp;e[i^1].v+=tmp;sum+=tmp; if (sum==f) return sum; } } if (!sum) dis[x]=-1; return sum; } inline void dinic() { while (bfs()) { F(i,1,t) cur[i]=head[i]; ans+=dfs(s,inf); } } inline bool check(int x,int y) { int tmp=x*x+y*y,rt=int(sqrt(tmp)); if (rt*rt!=tmp) return false; if (x