注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【网络流24题】【最小路径覆盖问题】【魔术球问题】  

2014-01-25 13:45:53|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   跟上一题一样,首先我们对这个题做这样的处理,对于一个球i,如果在它的上面放一个球J,且满足它们的和为完全平方数,那么就把它们连一条边,那么我们可以把问题转化成,对于N条路径,最多可以覆盖多少个点?这跟上面一个问题有点不同,但是我们可以转换一下,枚举能放多少个球,对于能放K个球,检验它是否可行,如果可行枚举K+1,不行的话答案就是K-1,那么如何检验呢?直接对这个图做最小路径覆盖即可,如果覆盖数小于等于N,那么则可行,否则不可行,然后就可以A了。然后关于优化,每一次K+1的时候实际上是新增一个节点,我们给新增的节点连边即可。然后对新图做网络流即可,不必再重新构图,然后求出来的最大流算到原来的答案中即可。
    这里由于动态添加点和边,所以咱可以定义0,1为源为汇,对于第N个点它的编号分别为N*2,和N*2+1.
    问题在于如何输出方案,这里显然要无视最后添加进去的节点。这里用了效率较低的重建图....另外为什么会这样的原因是因为咱是直接用残留网络构的图,实际上还是要加个流量和容量最好。这个以后再写,另外没加优化的DINIC后面的点2S左右.....
=====================================================================

program magicball;
const maxn=4000;
var g:array[0..maxn,0..maxn]of longint;
    f:array[0..maxn,0..maxn]of boolean;
    que,d:array[0..maxn]of longint;
    v:array[0..maxn]of boolean;
    n,m:longint;

procedure add(x,m:longint);
var i,u:longint;
begin
  u:=x shl 1;
  g[0][u]:=1;
  g[u xor 1][1]:=1;
  for i:=1 to m-1 do
   if sqr(trunc(sqrt(x+i)))=x+i then
     begin
       g[i shl 1][u xor 1]:=1;
       f[i shl 1][u xor 1]:=true;
     end;
end;

function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;

function bfs(s,t:longint):boolean;
var l,r,u,i:longint;
begin
  fillchar(v,sizeof(v),false);
  fillchar(d,sizeof(d),0);
  fillchar(que,sizeof(que),0);
  l:=0;r:=1;que[l]:=s;v[s]:=true;
  while l<r do
   begin
     u:=que[l];
     for i:=0 to m shl 1 xor 1 do
       if (g[u][i]>0)and(not v[i]) then
        begin
          que[r]:=i;
          inc(r);
          d[i]:=d[u]+1;
          v[i]:=true;
        end;
     inc(l);
   end;
  exit(v[t]);
end;

function dfs(p,a,t:longint):longint;
var f,flow,i:longint;
begin
  if (a=0)or(p=t) then exit(a);
  flow:=0;
  for i:=0 to m shl 1 xor 1 do
    if (g[p][i]>0)and(d[i]=d[p]+1) then
     begin
       f:=dfs(i,min(g[p][i],a),t);
       if f=0 then continue;
       inc(flow,f);
       dec(g[p][i],f);
       inc(g[i][p],f);
       dec(a,f);
       if a=0 then break;
     end;
  exit(flow);
end;

function dinic(s,t:longint):longint;
var maxflow:longint;
begin
  maxflow:=0;
  while bfs(s,t) do
   maxflow:=maxflow+dfs(s,maxlongint,t);
  exit(maxflow);
end;

procedure print(p:longint);
var i:longint;
begin
  write(p,' ');v[p shl 1]:=true;
  for i:=1 to m do
   if (g[p shl 1][i shl 1 xor 1]=0)and(f[p shl 1][i shl 1 xor 1])then
      print(i);
end;

procedure init;
var i,flow,min,now:longint;
begin
  read(n);
  for m:=1 to n do add(m,m);
  fillchar(f,sizeof(f),false);
  flow:=0;
  min:=n;
  repeat
    flow:=dinic(0,1);
    min:=min-flow;
    if min>n then break;
    inc(m);
    inc(min);
    add(m,m);
  until false;
  dec(m);
  writeln(m);
  fillchar(g,sizeof(g),0);
  for i:=1 to m do add(i,i);
  flow:=dinic(0,1);
  fillchar(v,sizeof(v),false);
  for i:=1 to m do
   if not v[i shl 1] then begin print(i);writeln;end;
end;

begin
  assign(output,'f.out');rewrite(output);
  init;
  close(output);
end.


  评论这张
 
阅读(25)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018