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

z55250825

一只蒟蒻

 
 
 

日志

 
 

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

2014-01-25 12:03:00|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    首先输出方案有多解,看算法怎么增广的了。
   有向无环图的最小路径覆盖问题,就是求出一个数目最少的有向路径集合,使得每一个点都只在这个集合的一条有向路径上。
  首先每一个点都只属于一个有向路径,代表了不会出现这种情况:
   【网络流24题】【最小路径覆盖】【最小路径覆盖问题】 - z55250825 - z55250825
       也就是说两条路径不可能交于同一个点。
       即:路径上除了终点以外,其余的点都只指向一个点。路径上除起点之外,其余的点都只被一个点指向。
       只要满足了这个条件就是一个可行解。那么我们就可以想到,每一个点都只连向一个点,这跟二分图的最大匹配实际上是十分相似的。因此,我们把一个点S拆成两个点 M N,然后假设两点有边相连我们就连一条容量为1的边,这样我们就得到了一个二分图,这个二分图的左边表示该点S向外指向,右边表示该点S被指向,那么在左边一个点P 连一条边 到右边的Q,它的意思实际上是存在一条路径有P到Q的边.
       以下来自某题解,写的更清楚些:

所以我们可以把每个顶点理解成两个顶点,一个是出发,一个是目标,建立二分图模型。该二分图的任何一个匹配方案,都对应了一个路径覆盖方案。如果匹配数为0,那么显然路径数=顶点数。每增加一条匹配边,那么路径覆盖数就减少一个,所以路径数=顶点数 - 匹配数。要想使路径数最少,则应最大化匹配数,所以要求二分图的最大匹配。

   然后就是求最大匹配,二分图的匈牙利可做,然后我们把左边连到一个源点S,容量为1,右边连到一个汇点T,容量也为1,这个显然表示的也是最大匹配,因为最后的最大匹配显然是满足这个网络流图的最大流的,假设它还不是最大匹配,那么我们就还存在一个更优的匹配,这个匹配所对应的流应该更大。所以就OK了。
   关于如何输出方案,只要沿着左边的点,找到残余网络中流为0的,然后再从右边到对应左边节点,然后再递归下去即可。
======================================================================

program minroad;
const maxn=1000;
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,ans,i:longint;

procedure init;
var i,j,u,v:longint;
begin
  read(n,m);
  fillchar(g,sizeof(g),0);
  fillchar(f,sizeof(f),false);
  for i:=1 to n do g[0][i]:=1;
  for i:=1 to n do g[i+n][n+n+1]:=1;
  for i:=1 to m do
   begin
     read(u,v);
     g[u][v+n]:=1;
     f[u][v+n]:=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(que,sizeof(que),0);
  fillchar(d,sizeof(d),0);
  fillchar(v,sizeof(v),false);
  l:=0;r:=1;que[l]:=s;v[s]:=true;
  while l<r do
   begin
     u:=que[l];
     for i:=0 to n+n+1 do
      if (g[u][i]>0)and(not v[i]) then
       begin
         que[r]:=i;
         inc(r);
         v[i]:=true;
         d[i]:=d[u]+1;
       end;
     inc(l);
   end;
  exit(v[t]);
end;

function dfs(p,a,t:longint):longint;
var i,f,flow:longint;
begin
  if (a=0)or(p=t) then exit(a);
  flow:=0;
  for i:=0 to n+n+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 ans:longint;
begin
  ans:=0;
  while bfs(s,t) do
     ans:=ans+dfs(s,maxlongint,t);
  exit(ans);
end;

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

begin
  assign(input,'f.in');reset(input);
  init;
  ans:=n-dinic(0,n+n+1);
  fillchar(v,sizeof(v),false);
  for i:=1 to n do if not v[i] then begin print(i);writeln;end;
  write(ans);
  close(input);
end.



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

历史上的今天

评论

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

页脚

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