首页 > 代码库 > BZOJ2661 （费用流）
BZOJ2661 （费用流）
把所有点拆成两个，将符合条件的两个点x,y连上边，流量为1，费用为-(x+y)。
做一遍最小费用最大流，最后ans div 2即可。
Program bzoj2661;const INF=2000000000;var last,next,p,cost,cap,q:array[0..1000000] of longint; flag1,flag2:array[0..10000] of boolean; a,c,i,j,x,y,t,s,sum:longint; b:array[0..1000000] of longint; pd:array[0..10000] of boolean; d,ps:array[0..10000] of longint;function gcd(x,y:longint):longint;begin if y=0 then exit(x) else exit(gcd(y,x mod y));end;procedure add(x,y,f,c:longint);begin inc(sum); next[sum]:=last[x]; last[x]:=sum; p[sum]:=y; q[sum]:=x; cost[sum]:=c; cap[sum]:=f;end;procedure adt(x,y,f,c:longint);begin add(x,y,f,c); add(y,x,0,-c);end;procedure spfa;var i,j,l,r:longint;begin for i:=0 to t do d[i]:=INF; fillchar(pd,sizeof(pd),false); l:=1; r:=1; pd[s]:=true; b[1]:=s; d[s]:=0; while l<=r do begin i:=last[b[l]]; while i<>0 do begin if (cap[i]>0) and (d[p[i]]>d[b[l]]+cost[i]) then begin d[p[i]]:=d[b[l]]+cost[i]; ps[p[i]]:=i; if not pd[p[i]] then begin inc(r); b[r]:=p[i]; pd[p[i]]:=true; end; end; i:=next[i]; end; pd[b[l]]:=false; inc(l); end;end;procedure minCmaxF;var x,i,j,cc,f,min:longint;begin f:=0; cc:=0; while true do begin spfa; if d[t]=INF then begin writeln(f div 2,‘ ‘,-cc div 2); exit; end; min:=INF; x:=t; while x<>s do begin if cap[ps[x]]<min then min:=cap[ps[x]]; x:=q[ps[x]]; end; x:=t; while x<>s do begin dec(cap[ps[x]],min); inc(cap[ps[x] xor 1],min); x:=q[ps[x]]; end; cc:=cc+min*d[t]; f:=f+min; end;end;begin readln(a,c); s:=0; for i:=a to c do for j:=a to c do if (i<>j) then begin x:=trunc(sqrt(abs(i*i-j*j))); if x*x<>abs(i*i-j*j) then continue; if gcd(i,j)<>1 then continue; add(i,j+c,1,-(i+j)); end; for i:=a to c do add(0,i,1,0); for i:=a to c do add(i+c,c*2+1,1,0); s:=0; t:=2*c+1; minCmaxF;end.
BZOJ2661 （费用流）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。