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：
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #define maxn 2005 7 #define maxm 1000000 8 #define inf 1061109567 9 using namespace std; 10 char ch; 11 bool ok; 12 void read(int &x){ 13 for (ok=0,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=1; 14 for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar()); 15 if (ok) x=-x; 16 } 17 int a,b; 18 bool bo1[maxn],bo2[maxn],bo[maxn]; 19 struct flow{ 20 int s,t,tot,now[maxn],son[maxm],pre[maxm],val[maxm],cost[maxm]; 21 int dis[maxn],head,tail,list[maxn],tmp,totflow,totcost; 22 bool bo[maxn]; 23 void init(){s=0,t=(b<<1)+1,tot=1,memset(now,0,sizeof(now));} 24 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;} 25 void add(int a,int b,int c,int d){put(a,b,c,d),put(b,a,0,-d);} 26 void spfa(){ 27 memset(bo,0,sizeof(bo)); 28 memset(dis,63,sizeof(dis)); 29 head=0,tail=1,list[1]=s,dis[s]=0,bo[s]=1; 30 while (head!=tail){ 31 if (++head==maxn) head=1; 32 int u=list[head]; 33 for (int p=now[u],v=son[p];p;p=pre[p],v=son[p]) 34 if (val[p]&&dis[v]>dis[u]+cost[p]){ 35 dis[v]=dis[u]+cost[p]; 36 if (!bo[v]){ 37 if (++tail==maxn) tail=1; 38 list[tail]=v,bo[v]=1; 39 } 40 } 41 bo[u]=0; 42 } 43 } 44 int dfs(int u,int rest,int totval){ 45 bo[u]=1; 46 if (u==t){totcost+=rest*totval;return rest;} 47 int ans=0; 48 for (int p=now[u],v=son[p];p&&rest;p=pre[p],v=son[p]) 49 if (val[p]&&!bo[v]&&dis[v]==dis[u]+cost[p]){ 50 int d=dfs(v,min(rest,val[p]),totval+cost[p]); 51 val[p]-=d,val[p^1]+=d,ans+=d,rest-=d; 52 } 53 return ans; 54 } 55 bool relax(){ 56 int d=inf; 57 for (int u=s;u<=t;u++) if (bo[u]) 58 for (int p=now[u],v=son[p];p;p=pre[p],v=son[p]) 59 if (val[p]&&!bo[v]) d=min(d,dis[u]+cost[p]-dis[v]); 60 if (d==inf) return false; 61 for (int u=s;u<=t;u++) if (!bo[u]) dis[u]+=d; 62 return true; 63 } 64 void work(){ 65 spfa(),totflow=totcost=0; 66 do{ 67 do{ 68 memset(bo,0,sizeof(bo)); 69 tmp=dfs(s,inf,0),totflow+=tmp; 70 }while (tmp); 71 }while (relax()); 72 } 73 }f; 74 int main(){ 75 read(a),read(b),f.init(); 76 for (int i=a;i<=b;i++) for (int j=a;j<i;j++){ 77 int t=round(sqrt(i*i-j*j)); 78 if (t*t==i*i-j*j&&__gcd(j,t)==1) bo[i]=1,bo[j]=1,f.add(i,j+b,1,-i-j),f.add(j,i+b,1,-i-j); 79 } 80 for (int i=a;i<=b;i++) if (bo[i]) f.add(f.s,i,1,0); 81 for (int i=a;i<=b;i++) if (bo[i]) f.add(i+b,f.t,1,0); 82 f.work(); 83 printf("%d %d ",f.totflow>>1,(-f.totcost)>>1); 84 return 0; 85 }