首页 > 代码库 > BZOJ2661: [BeiJing wc2012]连连看

BZOJ2661: [BeiJing wc2012]连连看

2024-07-16 15:57:00   224人阅读

2661: [BeiJing wc2012]连连看

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 483  Solved: 200
[Submit][Status]

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

题解：

好吧，最大费用最大流还是老老实实把费用取负吧。。。

各种不理解？怎么会是二分图呢？怎么这样简单粗暴就可以了？233

代码：

  1 const inf=maxlongint;  2 type node=record  3      from,go,next,v,c:longint;  4      end;  5 var e:array[0..2000000] of node;  6     pre,head,q,d,c1,c2:array[0..1000000] of longint;  7     v:array[0..1000000] of boolean;  8     i,j,n,s,t,l,r,mincost,tot,x,y,z,a,b,maxflow:longint;  9 function min(x,y:longint):longint; 10  begin 11  if x<y then exit(x) else exit(y); 12  end; 13 procedure ins(x,y,z,w:longint); 14  begin 15  inc(tot); 16  with e[tot] do 17   begin 18   from:=x;go:=y;v:=z;c:=w;next:=head[x];head[x]:=tot; 19   end; 20  end; 21 procedure insert(x,y,z,w:longint); 22  begin 23  ins(x,y,z,w);ins(y,x,0,-w); 24  end; 25 function spfa:boolean; 26  var i,x,y:longint; 27  begin 28  fillchar(v,sizeof(v),false); 29  for i:=s to t do d[i]:=inf; 30  l:=0;r:=1;q[1]:=s;d[s]:=0;v[s]:=true; 31  while l<r do 32   begin 33   inc(l);if l=1000000 then l:=0; 34   x:=q[l];v[x]:=false; 35   i:=head[x]; 36   while i<>0 do 37    begin 38    y:=e[i].go; 39    if (e[i].v<>0) and (d[x]+e[i].c<d[y]) then 40     begin 41     d[y]:=d[x]+e[i].c; 42     pre[y]:=i; 43     if not(v[y]) then 44      begin 45      v[y]:=true; 46      inc(r);if r=1000000 then r:=0; 47      q[r]:=y; 48      end; 49     end; 50    i:=e[i].next; 51   end; 52  end; 53  exit(d[t]<>inf); 54  end; 55 procedure mcf; 56  var i,tmp:longint; 57  begin 58  mincost:=0;maxflow:=0; 59  while spfa do 60   begin 61   tmp:=inf; 62   i:=pre[t]; 63   while i<>0 do 64    begin 65    tmp:=min(tmp,e[i].v); 66    i:=pre[e[i].from]; 67    end; 68   inc(mincost,tmp*d[t]); 69   inc(maxflow,tmp); 70   i:=pre[t]; 71   while i<>0 do 72    begin 73    dec(e[i].v,tmp); 74    inc(e[i xor 1].v,tmp); 75    i:=pre[e[i].from]; 76    end; 77   end; 78  end; 79 function gcd(x,y:longint):longint; 80  begin 81  if y=0 then exit(x) else exit(gcd(y,x mod y)); 82  end; 83  84 procedure init; 85  begin 86  tot:=1; 87  readln(a,b); 88  s:=0;t:=10000; 89  for i:=a to b do insert(s,i,1,0); 90  for i:=a to b do insert(i+b,t,1,0); 91  for i:=a to b do 92   for j:=a to b do 93    if (trunc(sqrt(abs(i*i-j*j)))=sqrt(abs(i*i-j*j))) and (i<>j) then 94     if gcd(trunc(sqrt(abs(i*i-j*j))),min(i,j))=1 then 95      insert(i,b+j,1,-i-j); 96  end; 97 procedure main; 98  begin 99  mincost:=0;100  mcf;101  writeln(maxflow>>1,‘ ‘,-mincost>>1);102  end;103 begin104  assign(input,‘input.txt‘);assign(output,‘output.txt‘);105  reset(input);rewrite(output);106  init;107  main;108  close(input);close(output);109 end.
View Code

 


联系
我们