2661: [BeiJing wc2012]连连看

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 1349  Solved: 577

[][][]

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

 

Source

 

拆点直接连边。跑最大费用最大流，答案/2。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 struct data { 9 int cost,w,to,next;10 }e[100000];11 int head[10000],cnt;12 int S,T; 13 void add(int u,int v,int w,int c) {14 e[cnt].to=v;e[cnt].next=head[u];e[cnt].w=w;e[cnt].cost=c;head[u]=cnt++;15 e[cnt].to=u;e[cnt].next=head[v];e[cnt].w=0;e[cnt].cost=-c;head[v]=cnt++;16 }17 int dis[10000];18 bool vis[10000];19 int q[10000],used;20 bool spfa() {21 memset(dis,-37,sizeof(dis));22 vis[T]=1;dis[T]=0;23 int h=0,t=1;24 q[0]=T;25 while(h!=t) {26 int now=q[h];h++;if(h==10000) h=0;27 for(int i=head[now];i>=0;i=e[i].next) {28 int to=e[i].to;if(!e[i^1].w) continue;29 if(dis[to]
            
             =0;i=e[i].next) {44 int to=e[i].to;45 if(!vis[to]&&e[i].w>0&&dis[to]==dis[x]+e[i].cost&&(f=dfs(to,min(e[i].w,a)))) {46 e[i].w-=f;e[i^1].w+=f;47 a-=f;flow+=f;48 if(a==0) break;49 }50 }51 return flow;52 }53 void zkw() {54 while(spfa()) {55 do {56 memset(vis,0,sizeof(vis));57 }while(dfs(S,2147483647));58 memset(vis,0,sizeof(vis));59 }60 }61 bool check(int x,int y) {62 int tmp=x*x-y*y,z=(int)sqrt(tmp); 63 if (z*z!=tmp) return false; 64 if (y