Description
凡是考智商的题里面总会有这么一种消除游戏。不过现在面对的这关连连看可不是QQ游戏里那种考眼力的游戏。我们的规则是，给出一个闭区间[a,b]中的全部整数，如果其中某两个数x,y（设x>y）的平方差x2-y2是一个完全平方数z2，并且y与z互质，那么就可以将x和y连起来并且将它们一起消除，同时得到x+y点分数。那么过关的要求就是，消除的数对尽可能多的前提下，得到足够的分数。快动手动笔算一算吧。
Input
只有一行，两个整数，分别表示a,b。
Output
两个数，可以消去的对数，及在此基础上能得到的最大分数。
Sample Input
1 15
Sample Output
2 34
HINT
对于30%的数据，1<=a,b<=100
对于100%的数据，1<=a,b<=1000
题解：
http://blog.csdn.net/aarongzk/article/details/50302219
code：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 2005
#define maxm 1000000
#define inf 1061109567
using namespace std;
char ch;
bool ok;
void read(int &x){
for (ok=,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=;
for (x=;isdigit(ch);x=x*+ch-'',ch=getchar());
if (ok) x=-x;
}
int a,b;
bool bo1[maxn],bo2[maxn],bo[maxn];
struct flow{
int s,t,tot,now[maxn],son[maxm],pre[maxm],val[maxm],cost[maxm];
int dis[maxn],head,tail,list[maxn],tmp,totflow,totcost;
bool bo[maxn];
void init(){s=,t=(b<<)+,tot=,memset(now,,sizeof(now));}
void put(int a,int b,int c,int d){pre[++tot]=now[a],now[a]=tot,son[tot]=b,val[tot]=c,cost[tot]=d;}
void add(int a,int b,int c,int d){put(a,b,c,d),put(b,a,,-d);}
void spfa(){
memset(bo,,sizeof(bo));
memset(dis,,sizeof(dis));
head=,tail=,list[]=s,dis[s]=,bo[s]=;
while (head!=tail){
if (++head==maxn) head=;
int u=list[head];
for (int p=now[u],v=son[p];p;p=pre[p],v=son[p])
if (val[p]&&dis[v]>dis[u]+cost[p]){
dis[v]=dis[u]+cost[p];
if (!bo[v]){
if (++tail==maxn) tail=;
list[tail]=v,bo[v]=;
}
}
bo[u]=;
}
}
int dfs(int u,int rest,int totval){
bo[u]=;
if (u==t){totcost+=rest*totval;return rest;}
int ans=;
for (int p=now[u],v=son[p];p&&rest;p=pre[p],v=son[p])
if (val[p]&&!bo[v]&&dis[v]==dis[u]+cost[p]){
int d=dfs(v,min(rest,val[p]),totval+cost[p]);
val[p]-=d,val[p^]+=d,ans+=d,rest-=d;
}
return ans;
}
bool relax(){
int d=inf;
for (int u=s;u<=t;u++) if (bo[u])
for (int p=now[u],v=son[p];p;p=pre[p],v=son[p])
if (val[p]&&!bo[v]) d=min(d,dis[u]+cost[p]-dis[v]);
if (d==inf) return false;
for (int u=s;u<=t;u++) if (!bo[u]) dis[u]+=d;
return true;
}
void work(){
spfa(),totflow=totcost=;
do{
do{
memset(bo,,sizeof(bo));
tmp=dfs(s,inf,),totflow+=tmp;
}while (tmp);
}while (relax());
}
}f;
int main(){
read(a),read(b),f.init();
for (int i=a;i<=b;i++) for (int j=a;j<i;j++){
int t=round(sqrt(i*i-j*j));
if (t*t==i*i-j*j&&__gcd(j,t)==) bo[i]=,bo[j]=,f.add(i,j+b,,-i-j),f.add(j,i+b,,-i-j);
}
for (int i=a;i<=b;i++) if (bo[i]) f.add(f.s,i,,);
for (int i=a;i<=b;i++) if (bo[i]) f.add(i+b,f.t,,);
f.work();
printf("%d %d\n",f.totflow>>,(-f.totcost)>>);
return ;
}