BZOJ3275 Number

2019-04-14 17:01发布

站内文章 / 模拟电子
10524 0 1763
偶数之间gcd不为1，显然 奇数^2加奇数^2不等于偶数^2，因为奇数可以写成2x+1的形式，所以奇数方模4余1，两个加一起余2，而偶数方模4余0 二分图，跑最小割即可 #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAXN 3010 #define MAXM 5000010 #define INF 1000000000000ll #define MOD 1000000007 #define ll long long #define eps 1e-8 struct vec{ int to; int fro; ll v; }; vec mp[MAXM]; int tai[MAXN],cnt=1; int s,t; int d[MAXN]; int q[MAXN],hd,tl; ll ans; int cur[MAXN]; inline void be(int x,int y,ll z){ mp[++cnt].to=y; mp[cnt].fro=tai[x]; tai[x]=cnt; mp[cnt].v=z; } inline void bse(int x,int y,ll z){ be(x,y,z); be(y,x,0); } bool bfs(){ int i,x,y; memset(d,0,sizeof(d)); d[s]=1; hd=tl=0; q[tl++]=s; while(hd!=tl){ x=q[hd++]; for(i=tai[x];i;i=mp[i].fro){ y=mp[i].to; if(mp[i].v&&(!d[y])){ d[y]=d[x]+1; q[tl++]=y; } } } return d[t]; } ll dfs(int x,ll mx){ if(x==t){ return mx; } ll i,y,tt; ll re=0; for(i=tai[x];i;i=mp[i].fro){ y=mp[i].to; if(d[y]==d[x]+1&&mp[i].v){ tt=dfs(y,min(mx,mp[i].v)); mp[i].v-=tt; mp[i^1].v+=tt; mx-=tt; re+=tt; if(!mx){ return re; } } } if(!re){ d[x]=0; } return re; } int n,m; ll a[MAXN],b[MAXN]; ll gcd(ll x,ll y){ return !y?x:gcd(y,x%y); } int main(){ int i,j,x,y,k,xx,yy; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%lld",&a[i]); } s=n+1; t=s+1; for(i=1;i<=n;i++){ if(a[i]&1){ bse(s,i,a[i]); }else{ bse(i,t,a[i]); } ans+=a[i]; for(j=1;j<=i;j++){ if((a[i]&1)==(a[j]&1)){ continue ; } if(gcd(a[i],a[j])==1&&((ll)sqrt(a[i]*a[i]+a[j]*a[j]))*((ll)sqrt(a[i]*a[i]+a[j]*a[j]))==a[i]*a[i]+a[j]*a[j]){ if(a[i]&1){ bse(i,j,INF); }else{ bse(j,i,INF); } } } } while(bfs()){ ans-=dfs(s,INF); } printf("%lld ",ans); return 0; } /* 2 1 2 3 5 */

热门文章