网易 
新闻 LOFTER 邮箱 相册 阅读 图书 有道 摄影 企业邮箱 优惠券 云笔记 闪电邮 邮箱大师 印像派 考拉海购
 
更多
博客 
手机博客 博客搬家 博客VIP服务 发现 小组 风格
 
群博客 博客油菜地 博客话题 博客热点 博客圈子 找朋友
 
登录  
 加关注
   显示下一条  |  关闭
温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

导航

 
 
 
 
 

日志

 
 
关于我
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.


  评论这张
 
阅读(78)| 评论(0)

历史上的今天

评论

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

页脚

我的照片书 - 手机博客 - 下载LOFTER APP - 订阅此博客

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