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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【vijos】【p1607】【植物大战僵尸】  

2014-03-04 22:51:14|  分类: 待处理题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
      题意依旧很长......

      给出一群植物,然后每一个plant 都有一个费用,所有的plant的攻击集合构成禁区,然后僵尸可以消灭植物,得到费用,要求不经过禁区,然后消灭一个植物其相应禁区消失,求可以得到的最大费用。

      首先这些植物可以构成一个“保护图”(个人YY...),假设某一个植物i在另一个植物j的攻击集合的内部,那么我们在j->i连一条边,表示j可以保护i。这个图的含义就是对于入度为0的点才能被攻击,否则不能被攻击,除非它的所有入度为0的点都被移除,每个点有个点权,为它的费用。然后咱们的任务就是在这个图里面选出一些点,满足:1.假设某个点被选了,那么所有指向它的点都要选。2.这些点的费用和最大。

     这个该怎么做?
     首先前提是知道了这道题的标签是网络流...

     首先是无责任的个人YY时间....首先 要满足条件1,咱们可以这样做,把每一个点拆成两个点,然后把每一个节点的容量设为 【入度,入度】,【0,0】两个区间,费用为 点权/入度,然后对于每一个入度为0的节点特殊处理为容量为1,与源点相连,然后每一个点都和汇点连一条容量为(入度-1)的边,跑最大费用流即可~正确性:1)保证了选择某一个节点它的入度都选。2)保证了选了某个节点它的费用就计算进去了。3)求的是最大费用。

     但是那个分两个区间的做法明显不可能(至少咱蒟蒻不会...目测也没有吧...)...所以咱就去 学(Zhao)习(Ban)下题解。

    发现咱之前想的模型是正确的...然后这个模型的学名叫做最大权闭合子图,闭合子图就是有向图中的一个子图,这个子图满足子图中的每一个点连出去的边都还是指向该子图中的点,然后最大权闭合子图就是这些闭合子图中点权最大的,而最大闭合子图显然就是各个点权都为1的特殊情形,所以咱们就只来考虑最大权闭合子图。这个模型显然就是最大权闭合子图。

    这个模型可以百度胡伯涛的论文最小割模型,写到这儿突然发现自己就是个傻×...太空飞行计划不就是一道最大权闭合子图问题吗?咱傻×的竟然不知道!!!而且还是在神犇讲课讲了三四次的情况下!!还特意提到了一般图的最大权闭合子图也可以做!!作为蒟蒻之前根本不知道.....今天自己刷的时候又突然YY懂了...

    太囧了。

    首先讲讲构网络流图。对于原来的那个 保护图 ,我们把它们之间的权值变成无穷大,然后建立源点和汇点,开始连边。对于正权的点,咱们将源点给它连一条容量为正权值的边,对于负权的点,咱们将它和汇点连一条容量为负权绝对值的边,然后对这个图跑网络流,答案就是 ∑正权点的权 - 最大流。
    为什么这样是对的咩??
    详细证明可以见 胡伯涛神犇的论文。

    这里就大致YY一下就可以了.....
    首先咱们可以知道,这里的最小割的每一条边 显然 其一个端点 是源点或者汇点 (因为所有两端无源点无汇点的边的容量都无穷大,不可能是最小割里面的边)这个的学术名词叫 简单割
     首先设 闭合图的点集 为 V ,其补集 为 V1,那么咱们可以证明 存在简单割的S集和T集 对应 V∪{s} 和 V1∪{T} ,这个很简单...直接反证即可,如果存在 一条边 从 u∈V 到 v∈V1,那么这个V 就不是闭合图了。
     上面证明了每一个闭合图对应一个简单割,现在咱们来证明每一个简单割对应一个闭合图。
     这个由割的性质也可以知道,所有在S割里面的点都不可能连向T割。所以是成立的,由上面两个证明咱们可以知道,简单割与闭合图一一对应。
     接下来咱们来证明更厉害的东西,那就是每一个最小割的容量对应其S闭合图的负点权 和 T闭合图的正点权 之和。
     因为简单割的每一个S闭合图内的割都是 源点连向 正点权,如果割源点和正点,那么显然这个正点权就属于T 闭合图了。同理如果割汇点与负点权的,那么负点权的点就属于S 闭合图了。
     这个还是看论文来的痛快....

     然后就可以AC了。

    注意一开始得按拓扑排序处理出那些肯定无敌的分量(就是可以从自己出发然后走回到自己的那些点,它们显然是无敌的了),这些点就不需要考虑了。然后再求最大流即可。实际上就是只用拓扑排序弄出来的点的诱导子图来构图把。

    然后注意闭合子图是某一个点连出去的必然在这个集合里,所以之前的那个保护图得把边全部反向才合法。(因为选了某个点可以不去选它所保护的节点)。

   这里还犯了一个模板错误,原来的模板是用邻接矩阵写的,各种裸,但是注意这句:
 if (0<e[tmp].w)and(d[e[tmp].v]=d[p]+1)then
      begin
        f:=dfs(e[tmp].v,min(a,e[tmp].w),t);
       if f=0 then continue;
  这里用在邻接矩阵可以,因为f=0 continue之后 会for 循环找新的邻接点,但是咱现在写的是邻接表,所以得手动更新邻接点,这里直接continue自然死循环...

   之后就是第8个点无限TLE...待修改...
==============================

program vijosp1607;
const maxm=400010;
      maxn=50000;
type edge=record
     u,v,w,pre:longint;
     end;
     arr=array[0..maxm]of edge;
     ar=array[0..maxn]of longint;

var e,oe:array[0..maxm]of edge;
    v:array[0..maxn+1]of boolean;
    que,d,last,ll,du:array[0..maxn]of longint;
    w:array[0..maxn]of longint;
    tot,n,m,ans:longint;

function calc(u,v:longint):longint;
begin
  exit((u-1)*m+v);
end;

procedure addedge(u,v,w:longint;var e:arr;var last:ar);
begin
  inc(tot);
  e[tot].u:=u;
  e[tot].v:=v;
  e[tot].w:=w;
  e[tot].pre:=last[u];
  last[u]:=tot;
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,tmp:longint;
begin
  fillchar(que,sizeof(que),0);
  fillchar(v,sizeof(v),false);
  fillchar(d,sizeof(d),0);
  l:=0;r:=1;que[l]:=s;v[s]:=true;
  while l<>r do
   begin
     u:=que[l];
     tmp:=last[u];
     while tmp<>-1 do
      begin
        if (e[tmp].w>0)and(not v[e[tmp].v]) then
         begin
           d[e[tmp].v]:=d[u]+1;
           v[e[tmp].v]:=true;
           que[r]:=e[tmp].v;
           inc(r);
         end;
        tmp:=e[tmp].pre;
      end;
     inc(l);
   end;
  exit(v[t]);
end;

function dfs(p,a,t:longint):longint;
var tmp,f,flow:longint;
begin
  if (p=t)or(a=0) then exit(a);
  tmp:=last[p];
  flow:=0;
  while tmp<>-1 do
   begin
     if (0<e[tmp].w)and(d[e[tmp].v]=d[p]+1)then
      begin
        f:=dfs(e[tmp].v,min(a,e[tmp].w),t);
        if f<>0 then
        begin
        dec(e[tmp].w,f);
        inc(e[tmp xor 1].w,f);
        inc(flow,f);
        dec(a,f);
        if a=0 then break;
        end;
      end;
     tmp:=e[tmp].pre;
   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 top;
var i,l,r,tmp,sav,u:longint;
begin
  fillchar(que,sizeof(que),0);
  fillchar(v,sizeof(v),false);
  l:=0;r:=0;
  for i:=1 to n*m do
   if du[i]=0 then
    begin
      que[r]:=i;
      v[i]:=true;
      inc(r);
    end;
  while l<>r do
   begin
     u:=que[l];
     tmp:=ll[u];
     while tmp<>0 do
      begin
        dec(du[oe[tmp].v]);
        if du[oe[tmp].v]=0 then
         begin
           que[r]:=oe[tmp].v;
           inc(r);
           v[oe[tmp].v]:=true;
         end;
        tmp:=oe[tmp].pre;
      end;
     inc(l);
   end;
  sav:=tot;
  tot:=-1;
  ans:=0;
  fillchar(last,sizeof(last),255);
  for i:=1 to sav do
   if (v[oe[i].u])and(v[oe[i].v]) then
    begin
      addedge(oe[i].v,oe[i].u,maxlongint,e,last);
      addedge(oe[i].u,oe[i].v,0,e,last);
    end;
  for i:=1 to n*m do
   if v[i] then
     begin
       if w[i]>0 then
        begin
          addedge(0,i,w[i],e,last);
          addedge(i,0,0,e,last);
          inc(ans,w[i]);
        end
       else
        begin
          addedge(i,maxn,-w[i],e,last);
          addedge(maxn,i,0,e,last);
        end;
     end;
end;

procedure init;
var i,j,k,q,uu,vv,ww,now,next:longint;

begin
  read(n,m);
  tot:=0;
  fillchar(ll,sizeof(ll),0);
  fillchar(du,sizeof(du),0);e
  ans:=0;
  for i:=1 to n do
    for j:=1 to m do
     begin
       now:=calc(i,j);
       read(w[now]);
       read(q);
       if j>1 then
       begin
        addedge(now,now-1,1,oe,ll);
        inc(du[now-1]);
       end;
       for k:=1 to q do
        begin
          read(uu,vv);
          inc(uu);inc(vv);
          next:=calc(uu,1);
          for ww:=0 to vv-1 do
           begin
            addedge(now,next+ww,1,oe,ll);
            inc(du[next+ww]);
           end;
        end;
     end;
  top;
  writeln(ans-dinic(0,maxn));
end;

begin
  assign(input,'pvz9.in');reset(input);
  init;
  close(input);
end.






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

历史上的今天

评论

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

页脚

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