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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【网络流24题】【二分图最大点权独立集】【方格取数问题】  

2014-01-25 23:38:35|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   首先这个在二分图里面看过了,所以非常容易想出算法来。
   没有公共边实际上就是不相邻,我们可以把这个图相间的染色,然后白色的放左边,黑色的放右边,每个点有点权,然后我们如果两点相邻则连一条边,那么问题变成了,从这个二分图中选出最多的点,使得它们并没有边相连,且点权和加起来最大。这个模型中的点集叫做独立集,然后咱们再来介绍下覆盖集,覆盖集即从二分图中选出点,使得二分图的每一条边的某一个端点都在这个覆盖集中,最小点权覆盖集就是满足条件的点权和最小的。而最小点权覆盖集又可以转换为最小割模型解决,最小割等于最大流(好绕...),关键在倒数第二步,为什么最小点权覆盖集可以转化为最小割模型,我们可以这样子构图从而把点权转化为流量,对于左边,建源点S,将它们与S连边,容量为各自点权,然后对于右边,建汇点T,将它们与T连边,容量为各自点权,然后原二分图上容量为无限大,这样子,假设我们存在增广路,实际上的意思就是存在有一条边,它的两个端点是没有被覆盖的,所以所有的边都被覆盖的条件即:图中不存在增广路,即图不连通,所以这就是一个割,然后最小割实际上就是点权和最小的,所以最大流=最小点权覆盖
       接下来呢?最小点权覆盖集实际上和最大点权独立集是互补的.....也就是说最大点权独立=总点权-最小点权覆盖。
       至此,可以AC了...
       这里对于 [i,j]的点,我们给它建 (i-1)*m+j 即可。
====================================================

program flow9;
const maxn=500;
var
  g,a:array[0..maxn,0..maxn]of longint;
  que,d:array[0..maxn]of longint;
  v:array[0..maxn]of boolean;
  n,m:longint;

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

function bfs(s,t:longint):boolean;
var i,u,l,r: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*m+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 f,flow,i:longint;
begin
  if (p=t)or(a=0) then exit(a);
  flow:=0;
  for i:=0 to n*m+1 do
   if (g[p][i]>0)and(d[i]=d[p]+1) then
    begin
      f:=dfs(i,min(a,g[p][i]),t);
      if f=0 then continue;
      inc(flow,f);
      inc(g[i][p],f);
      dec(g[p][i],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 init;
var i,j,ans,tot:longint;
begin
  read(n,m);
  fillchar(g,sizeof(g),255);
  tot:=0;
  for i:=1 to n do
    for j:=1 to m do
       begin
        read(a[i][j]);
        tot:=tot+a[i][j];
       end;
  for i:=1 to n do
    for j:=1 to m do
     if (i+j)and 1=0 then
      begin
        g[0][(i-1)*m+j]:=a[i][j];
        g[(i-1)*m+j][0]:=0;
        if i>1 then
         begin
           g[(i-1)*m+j][(i-2)*m+j]:=maxlongint;
           g[(i-2)*m+j][(i-1)*m+j]:=0;
         end;
        if i<n then
         begin
           g[(i-1)*m+j][i*m+j]:=maxlongint;
           g[i*m+j][(i-1)*m+j]:=0;
         end;
        if j>1 then
         begin
           g[(i-1)*m+j][(i-1)*m+j-1]:=maxlongint;
           g[(i-1)*m+j-1][(i-1)*m+j]:=0;
         end;
        if j<m then
         begin
           g[(i-1)*m+j][(i-1)*m+j+1]:=maxlongint;
           g[(i-1)*m+j+1][(i-1)*m+j]:=0;
         end;
      end
     else
      begin
        g[(i-1)*m+j][n*m+1]:=a[i][j];
        g[n*m+1][(i-1)*m+j]:=0;
      end;
  ans:=dinic(0,n*m+1);
  ans:=tot-ans;
  write(ans);
end;

begin
  init;
end.

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

历史上的今天

评论

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

页脚

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