BZOJ 3275: Number

2019-04-13 21:21发布

站内文章 / 模拟电子
11369 0 1798

题目分析：

两个点同时选会有inf的代价，需要满足二分图性质
  • 两个偶数的gcd不为1
  • 两个奇数的平方和不可能是完全平方数，因为奇数可以写成2k+1, 平方模4余1，两个平方的和模4余2且为偶数，而偶数的平方模4余0，所以不可能是平方数
所以两个不能同时选的数一定是一奇一偶，二分图，加上权值跑最小割即可 #include #include #include #include #include #include #define LL long long #define maxn 3005 #define maxm 1000005 using namespace std; char cb[1<<15],*cs,*ct; #define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<15,stdin),cs==ct)?0:*cs++) inline void read(int &a){ char c;bool f=0; while(!isdigit(c=getc())) if(c=='-') f=1; for(a=c-'0';isdigit(c=getc());a=a*10+c-'0'); if(f) a=-a; } const int inf = 0x3f3f3f3f; int n,m,S,T; int fir[maxn],cur[maxn],dis[maxn],nxt[maxm],to[maxm],tot=1,cap[maxm],sum; inline void line(int x,int y,int z,int rz=0){ nxt[++tot]=fir[x],fir[x]=tot,to[tot]=y,cap[tot]=z; nxt[++tot]=fir[y],fir[y]=tot,to[tot]=x,cap[tot]=rz; } queue<int>q; bool bfs() { memset(dis,0,(T+1)<<2); dis[T]=1,q.push(T); while(!q.empty()){ int u=q.front();q.pop(); for(int i=fir[u];i;i=nxt[i]) if(cap[i^1]&&!dis[to[i]]){ dis[to[i]]=dis[u]+1; q.push(to[i]); } } return dis[S]; } int dfs(int u,int lim) { if(u==T) return lim; int need=lim,delta; for(int &i=cur[u];i;i=nxt[i]) if(cap[i]&&dis[u]==dis[to[i]]+1){ delta=dfs(to[i],min(cap[i],need)); cap[i]-=delta,cap[i^1]+=delta; if(!(need-=delta)) break; } return lim-need; } int Dinic(){ int flow=0; while(bfs()) memcpy(cur,fir,(T+1)<<2),flow+=dfs(S,inf); return flow; } int a[maxn],in[maxn]; inline bool check(int x){int y=int(sqrt(x));return y*y==x;} inline int gcd(int a,int b){return b?gcd(b,a%b):a;} int main() { read(n);S=0,T=n+1; for(int i=1;i<=n;i++){ read(a[i]),sum+=a[i]; if(a[i]&1) line(S,i,a[i]); else line(i,T,a[i]); for(int j=i-1;j>=1;j--) if(check(a[i]*a[i]+a[j]*a[j])&&gcd(a[i],a[j])==1){ if(a[i]&1) line(i,j,inf); else line(j,i,inf); } } printf("%d",sum-Dinic()); }

热门文章