二分图。赤果果的费用流。其实是KM。但是不会写。只好写费用流替代了。
先O(n^2)判哪些数对(x,y)可行。然后连边,做最大费用流。
因为每个数只能取一次。那么我把(x,y)和(y,x)都连了一遍。那么结果除以二。
判断选了几对,只要看T点的流量有多少不是从TT流过来的就行了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxm=5000000,inf=1061109567; int h[10005],p[maxm],c[maxm],cost[maxm],n1[maxm],q[maxm],sp[10005],inq[10005]; int sq[1000005]={0},S,T,TT,An=0,path[maxm],pre[10005],tot=0; inline void ae(int a,int b,int cc,int co){ p[tot]=b; c[tot]=cc; cost[tot]=co; n1[tot]=h[a]; h[a]=tot++; p[tot]=a; c[tot]=0; cost[tot]=-co; n1[tot]=h[b]; h[b]=tot++; }inline int spfa(){ memset(sp,63,sizeof(sp)); memset(inq,0,sizeof(inq)); int head=0,tail=1; sp[S]=0; q[0]=S; inq[S]=1; pre[S]=-1; while(head!=tail){ int u=q[head++]; if(head>=maxm) head-=maxm; inq[u]=0; for(int i=h[u];~i;i=n1[i]) if(c[i]>0&&sp[p[i]]>sp[u]+cost[i]){ path[p[i]]=i, pre[p[i]]=u, sp[p[i]]=sp[u]+cost[i]; if(!inq[p[i]]){ inq[p[i]]=1, q[tail++]=p[i]; if(tail>=maxm) tail-=maxm;} } }return sp[T]!=inf; }inline int aug(){ int delta=inf, flow=0; for(int i=T;pre[i]!=-1;i=pre[i]) delta=min(delta,c[path[i]]); for(int i=T;pre[i]!=-1;i=pre[i]){ c[path[i]]-=delta, c[path[i]^1]+=delta; flow+=cost[path[i]]*delta; }return flow; }inline int cf(){ int ret=0; while(spfa()) ret+=aug(); return ret; }int gcd(int a,int b){ return (!b)?a:gcd(b,a%b); }int main(){ int a,b; scanf("%d%d",&a,&b); memset(h,-1,sizeof(h)); for(int i=1;i<=1000;i++) sq[i*i]=i; S=0;TT=(b-a+1)<<1|1;T=TT+1; for(int i=a;i<=b;i++) for(int j=i+1;j<=b;j++) if(sq[j*j-i*i]&&gcd(sq[j*j-i*i],i)==1){ ae(j-a+1,b-a+1+i-a+1,1,-i-j); ae(i-a+1,b-a+1+j-a+1,1,-i-j); }ae(TT,T,inf,0); for(int i=1;i<=b-a+1;i++) ae(S,i,1,0), ae(i,TT,1,0), ae(b-a+1+i,T,1,0); int An1,An2=-cf(); for(int i=h[T];~i;i=n1[i]) if(p[i]==TT)An=b-a+1-c[i]; printf("%d %d\n",An>>1,An2>>1); return 0; }