【BZOJ2661】[BeiJing wc2012]连连看

#include <cstdio>#include <cstring>#include <queue>#include <iostream>#include <cmath>#define SQ(_) ((int)(sqrt(_)+1e-6)*(int)(sqrt(_)+1e-6)==_)using namespace std;int n,cnt,ans,sum,minn;int head[2010],next[2000000],cost[2000000],flow[2000000],to[2000000];int dis[2010],re[2010],rv[2010],inq[2010];queue<int> q;int gcd(int a,int b){	return (b==0)?a:gcd(b,a%b);}void add(int a,int b,int c){	to[cnt]=b,cost[cnt]=c,flow[cnt]=1,next[cnt]=head[a],head[a]=cnt++;	to[cnt]=a,cost[cnt]=-c,flow[cnt]=0,next[cnt]=head[b],head[b]=cnt++;}int bfs(){	int i,u;	memset(dis,0x3f,sizeof(dis));	q.push(0),dis[0]=0;	while(!q.empty())	{		u=q.front(),q.pop();		inq[u]=0;		for(i=head[u];i!=-1;i=next[i])		{			if(flow[i]&&dis[to[i]]>dis[u]+cost[i])			{				dis[to[i]]=dis[u]+cost[i];				re[to[i]]=i,rv[to[i]]=u;				if(!inq[to[i]])				{					q.push(to[i]);					inq[to[i]]=1;				}			}		}	}	return dis[2*n+1]<0;}int main(){	int i,j,a,b;	memset(head,-1,sizeof(head));	scanf("%d%d",&a,&b);	n=b-a+1;	for(i=a;i<=b;i++)		for(j=a;j<i;j++)			if(SQ(i*i-j*j)&&gcd(i,j)==1)				add(i-a+1,j-a+1+n,-i-j),add(j-a+1,i-a+1+n,-i-j);	for(i=1;i<=n;i++)	add(0,i,0),add(i+n,2*n+1,0);	while(bfs())	{		minn=1<<30;		for(i=2*n+1;i;i=rv[i])	minn=min(minn,flow[re[i]]);		sum+=minn,ans+=minn*dis[2*n+1];		for(i=2*n+1;i;i=rv[i])	flow[re[i]^1]+=minn,flow[re[i]]-=minn;	}	printf("%d %d",sum>>1,-ans>>1);	return 0;}