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
代码：
const inf=maxlongint;
type node=record
from,go,next,v,c:longint;
end;
var e:array[..] of node;
pre,head,q,d,c1,c2:array[..] of longint;
v:array[..] of boolean;
i,j,n,s,t,l,r,mincost,tot,x,y,z,a,b,maxflow:longint;
function min(x,y:longint):longint;
begin
if x<y then exit(x) else exit(y);
end;
procedure ins(x,y,z,w:longint);
begin
inc(tot);
with e[tot] do
begin
from:=x;go:=y;v:=z;c:=w;next:=head[x];head[x]:=tot;
end;
end;
procedure insert(x,y,z,w:longint);
begin
ins(x,y,z,w);ins(y,x,,-w);
end;
function spfa:boolean;
var i,x,y:longint;
begin
fillchar(v,sizeof(v),false);
for i:=s to t do d[i]:=inf;
l:=;r:=;q[]:=s;d[s]:=;v[s]:=true;
while l<r do
begin
inc(l);if l= then l:=;
x:=q[l];v[x]:=false;
i:=head[x];
while i<> do
begin
y:=e[i].go;
if (e[i].v<>) and (d[x]+e[i].c<d[y]) then
begin
d[y]:=d[x]+e[i].c;
pre[y]:=i;
if not(v[y]) then
begin
v[y]:=true;
inc(r);if r= then r:=;
q[r]:=y;
end;
end;
i:=e[i].next;
end;
end;
exit(d[t]<>inf);
end;
procedure mcf;
var i,tmp:longint;
begin
mincost:=;maxflow:=;
while spfa do
begin
tmp:=inf;
i:=pre[t];
while i<> do
begin
tmp:=min(tmp,e[i].v);
i:=pre[e[i].from];
end;
inc(mincost,tmp*d[t]);
inc(maxflow,tmp);
i:=pre[t];
while i<> do
begin
dec(e[i].v,tmp);
inc(e[i xor ].v,tmp);
i:=pre[e[i].from];
end;
end;
end;
function gcd(x,y:longint):longint;
begin
if y= then exit(x) else exit(gcd(y,x mod y));
end; procedure init;
begin
tot:=;
readln(a,b);
s:=;t:=;
for i:=a to b do insert(s,i,,);
for i:=a to b do insert(i+b,t,,);
for i:=a to b do
for j:=a to b do
if (trunc(sqrt(abs(i*i-j*j)))=sqrt(abs(i*i-j*j))) and (i<>j) then
if gcd(trunc(sqrt(abs(i*i-j*j))),min(i,j))= then
insert(i,b+j,,-i-j);
end;
procedure main;
begin
mincost:=;
mcf;
writeln(maxflow>>,' ',-mincost>>);
end;
begin
assign(input,'input.txt');assign(output,'output.txt');
reset(input);rewrite(output);
init;
main;
close(input);close(output);
end.