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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1066】【SCOI2007】【蜥蜴】  

2014-03-24 10:54:16|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   bzoj1065又是一届DP神题,先跳过233。
   题目大意:
   平面一群蜥蜴加一群柱子,一柱子只能容纳一蜥蜴,蜥蜴可以跳不超过D的距离,然后每个柱子经过一个蜥蜴,高度-1,高度变成0的时候消失,蜥蜴跳到平面外算逃脱成功,问最多可以逃脱多少只蜥蜴。
   
    一眼最大流....每一个柱子拆两个点,中间连这个柱子的高度,然后其中一个点表示跳进来,一个点表示跳出去。然后给所有有蜥蜴的柱子的跳进来的点连容量为这个柱子蜥蜴数目的点,然后边界与可以跳出边界的点相连,跑最大流即可。
==========================================

program bzoj1066;
const maxr=26;
      maxn=10000;
      maxm=30000;
type edge=record
     v,w,pre:longint;
     end;

var e:array[0..maxm]of edge;
    h:array[0..maxr,0..maxr]of longint;
    last,d,que:array[0..maxn]of longint;
    v:array[0..maxn]of boolean;
    n,m,num,dd,tot:longint;

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

procedure addedge(u,v,w:longint);
begin
  inc(tot);e[tot].v:=v;e[tot].w:=w;
  e[tot].pre:=last[u];last[u]:=tot;
  inc(tot);e[tot].v:=u;e[tot].w:=0;
  e[tot].pre:=last[v];last[v]:=tot;
end;

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

function max(a,b:longint):longint;
begin
  if a>b then exit(a) else exit(b);
end;

function bfs(s,t:longint):boolean;
var tmp,l,r,u:longint;
begin
  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
          v[e[tmp].v]:=true;
          d[e[tmp].v]:=d[u]+1;
          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 (e[tmp].w>0)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(a,f);
           dec(e[tmp].w,f);
           inc(e[tmp xor 1].w,f);
           inc(flow,f);
           if a=0 then break;
         end;
      end;
     tmp:=e[tmp].pre;
   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 init;
var i,j,k,l:longint;
    ch:char;
begin
  readln(n,m,dd);
  fillchar(last,sizeof(last),255);
  tot:=-1;
  for i:=1 to n do
   for j:=1 to m do
    begin
     read(ch);
     h[i][j]:=ord(ch)-ord('0');
     if h[i][j]<>0 then
       addedge(calc(i,j)shl 1-1,calc(i,j)shl 1,h[i][j]);
     if j=m then readln;
    end;
  for i:=1 to n do
   for j:=1 to m do
    if h[i][j]<>0 then
     begin
       for k:=1 to n do
        for l:=1 to m do
         if (h[k][l]<>0)and(sqrt((i-k)*(i-k)+(j-l)*(j-l))<=dd)then
          addedge(calc(i,j)shl 1,calc(k,l)shl 1-1,maxlongint);
       if (i-dd<=0)or(i+dd>n)or(j-dd<=0)or(j+dd>m) then
          addedge(calc(i,j)shl 1,maxn,maxlongint);
     end;
  num:=0;
  for i:=1 to n do
   for j:=1 to m do
     begin
       read(ch);
       if ch='L' then
        begin
         addedge(0,calc(i,j)shl 1-1,1);
         inc(num);
        end;
       if j=m then readln;
     end;
  writeln(num-dinic(0,maxn));
end;

begin
  init;
end.

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

历史上的今天

评论

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

页脚

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