[BJOI2012]连连看

题目描述
凡是考智商的题里面总会有这么一种消除游戏。不过现在面对的这关连连看可不是QQ游戏里那种考眼力的游戏。我们的规则是，给出一个闭区间[a,b]中的全部整数，如果其中某两个数x,y（设x>y）的平方差x^2-y2是一个完全平方数z^2，并且y与z互质，那么就可以将x和y连起来并且将它们一起消除，同时得到x+y点分数。那么过关的要求就是，消除的数对尽可能多的前提下，得到足够的分数。快动手动笔算一算吧。

输入格式
只有一行，两个整数，分别表示a,b。

输出格式
两个数，可以消去的对数，及在此基础上能得到的最大分数。

输入输出样例
输入 #1 复制

1 15

输出 #1 复制

2 34

说明/提示
对于30%的数据，1<=a,b<=100

对于100%的数据，1<=a,b<=1000

题意十分简单。
这道题我们要保证两个东西：

• 每个数字只会用一次。
• 两个数字一起消除。

所以我们建图只要保证上面的条件即可，然后跑费用流。

怎么保证呢？还是同样的套路，拆点，我们把每个数字拆成入点和出点，对于每个数字，我们源点S连向入点，出点连向汇点T，且流量都为1；对于满足要求的一组数字，我们让x的入点连向y的出点，y的入点，连向x的出点。

为什么呢？主要是保证每个数字用一次，因为我们把数字拆开了，那么可能同一个数字的入点和出点不是匹配的同一个数字，这样我们能保证匹配到同一个数字，但是我们计算是×2了，最后除以2即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int l,r,s,t,v[N],e[N],d[N];
int head[N<<4],nex[N<<4],to[N<<4],w[N<<4],flow[N<<4],tot=1;
inline void ade(int a,int b,int c,int d){
	to[++tot]=b; w[tot]=d; flow[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c,int d){
	ade(a,b,c,d);	ade(b,a,0,-d);
}
int spfa(){
	memset(d,0xcf,sizeof d);	d[s]=0;	queue<int> q;	q.push(s);
	int vis[N]={0};	vis[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(flow[i]&&d[to[i]]<d[u]+w[i]){
				d[to[i]]=d[u]+w[i];
				v[to[i]]=u;	e[to[i]]=i;
				if(!vis[to[i]])	q.push(to[i]),vis[to[i]]=1;
			}
		}
	}
	return d[t]!=0xcfcfcfcf;
}
void EK(){
	int res=0,maxflow=0;
	while(spfa()){
		int mi=0x3f3f3f3f;
		for(int i=t;i!=s;i=v[i])	mi=min(mi,flow[e[i]]);
		for(int i=t;i!=s;i=v[i])	flow[e[i]]-=mi,flow[e[i]^1]+=mi;
		maxflow+=mi;	res+=mi*d[t];
	}
	cout<<maxflow/2<<' '<<res/2<<endl;
}
signed main(){
	cin>>l>>r;	s=0; t=r*2+1;
	for(int i=l;i<=r;i++){
		for(int j=i+1;j<=r;j++){
			if(__gcd(i,j)!=1)	continue;
			int k=j*j-i*i;	if((int)sqrt(k)*(int)sqrt(k)!=k)	continue;
			add(i,j+r,1,i+j);	add(j,i+r,1,i+j);
		}
	}
	for(int i=l;i<=r;i++)	add(s,i,1,0),add(i+r,t,1,0);
	EK();
	return 0;
}