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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【vijos】【p1653】【疯狂的方格取数】  

2014-03-04 13:27:57|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
     突然想起这题以前走两次的时候那个四维动规愣是想不出....
     建图类似 数字梯形 问题,然后跑网络流即可。给每一个点拆点拆1对,连两条边,一条容量1,费用为权重,一条容量n-1,费用0,然后跑最大费用最大流。
================================================

program vijosp1653;
const maxm=50000;
type
  edge=record
  u,v,w,c,pre:longint;
  end;

var
  e:array[0..maxm]of edge;
  last,que,d,low,pre:array[0..maxm]of longint;
  v:array[0..maxm]of boolean;
  w:array[0..100,0..100]of longint;
  tot,n,m,ti:longint;
  cost:int64;

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

procedure addedge(u,v,w,c:longint);
begin
  inc(tot);
  e[tot].u:=u;
  e[tot].v:=v;
  e[tot].w:=w;
  e[tot].c:=c;
  e[tot].pre:=last[u];
  last[u]:=tot;
  inc(tot);
  e[tot].u:=v;
  e[tot].v:=u;
  e[tot].w:=0;
  e[tot].c:=-c;
  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 spfa(s,t:longint):boolean;
var l,r,tmp,aug,u:longint;
begin
  fillchar(d,sizeof(d),254);
  fillchar(pre,sizeof(pre),0);
  fillchar(que,sizeof(que),0);
  fillchar(v,sizeof(v),false);
  v[s]:=true;d[s]:=0;
  low[s]:=maxlongint;low[t]:=low[s];
  l:=0;r:=1;
  que[l]:=s;
  while l<>r do
   begin
     u:=que[l];
     tmp:=last[u];
     while tmp<>-1 do
      begin
        if (e[tmp].w>0)and(d[e[tmp].v]<d[u]+e[tmp].c) then
         begin
           d[e[tmp].v]:=d[u]+e[tmp].c;
           low[e[tmp].v]:=min(low[u],e[tmp].w);
           pre[e[tmp].v]:=tmp;
           if not v[e[tmp].v] then
            begin
              que[r]:=e[tmp].v;
              r:=(r+1)mod maxm;
              v[e[tmp].v]:=true;
            end;
         end;
        tmp:=e[tmp].pre;
      end;
     v[u]:=false;
     l:=(l+1)mod maxm;
   end;
  if low[t]=maxlongint then exit(false);
  cost:=cost+low[t]*d[t];
  u:=t;aug:=low[t];
  while u<>s do
   begin
     dec(e[pre[u]].w,aug);
     inc(e[pre[u] xor 1].w,aug);
     u:=e[pre[u]].u;
   end;
  exit(true);
end;

procedure init;
var i,j,k,u:longint;
begin
  read(ti,m,n);
  tot:=-1;
  fillchar(last,sizeof(last),255);
  for i:=1 to n do
   for j:=1 to m do
    begin
      read(w[i][j]);
      k:=calc(i,j);
      addedge(k shl 1-1,k shl 1,1,w[i][j]);
      addedge(k shl 1-1,k shl 1,ti-1,0);
    end;
  for i:=1 to n do
   for j:=1 to m do
    begin
      if j<m then
       begin
         k:=calc(i,j);
         u:=calc(i,j+1);
         addedge(k shl 1,u shl 1-1,ti,0);
       end;
      if i<n then
       begin
         k:=calc(i,j);
         u:=calc(i+1,j);
         addedge(k shl 1,u shl 1-1,ti,0);
       end;
    end;
  addedge(0,1,ti,0);
  addedge(calc(n,m),calc(n,m) shl 1+1,ti,0);
  cost:=0;
  while spfa(0,calc(n,m)shl 1) do;
  write(cost);
end;

begin
  init;
end.

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

历史上的今天

评论

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

页脚

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