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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【vijos】【p1726】【美食节】  

2014-03-03 21:22:02|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
     题面还是依旧不可直视的长...
     所以先来梳理题意,N种食物,M个厨师,第i个厨师做第j种食品1份代价为Tij,然后给出pi个人点了第i份食品(1<=i<=n),然后求分配做菜方案及做菜顺序,使所有人等待的总时间最少。(假设某个人的食品在第 i 个厨师的做菜顺序的 第 j 个,那么他等待的时间就是该厨师做前j个菜的时间)
     我们可以无视点菜的人,实际上就是菜与厨师的较量。
     问题进一步简化下,(这里有点口胡,欢迎跳过)就是 给你 M个厨师,N种食物,求食物的一个划分以及一个顺序,该划分下每一个食物得到一个代价,该顺序下第k位的食物还可以得到k的加权,总代价为 每一个划分下每一食物的 代价乘以权 的和。然后求总代价最小。
    首先考虑已经得到了划分,那么怎么求顺序?
    显然这个问题是个贪心的结局....即大的优先排前面,小的排后面。
    那么接下来就是考虑划分。
    首先得保证有那么多的菜,怎么保证?一般想到的都是最大流把....,我们建立一个汇点,然后每一个菜建立一个接收点,接收厨师做好的菜,容量为它所需要的。然后由于跑的最大流所以每一个点的容量都会满流。
    这里就是把菜看做了流。
    咱有个奇葩的想法就是...把每一个厨师 都 拆成 P个点,表示做第P份菜的厨师~然后对于第P份菜的厨师连边就非常轻松了,然后跑费用流....
   但是一看p=800,m=100.....拆出来有80000个克隆厨师.......这估计是跑不完了....
   果断不会了....
   然后看了一下网上的各种题解,动态加点...
   四个字,别人容易吗.....
   然后想起做网络流24题的时候,魔术球啥的题目...突然感觉知道了...
   先是原来的静态的做法。
   (咱之前想的的确有些地方太单纯了....)
    首先正着考虑做菜不太好,因为我们不知道这个厨师做菜的上限是多少(就是某个菜会使之后多少人等待),所以我们倒着考虑加菜第i次厨师j的菜就是厨师j做的倒数第i样菜,最后一样菜的代价显然只会让最后一个人等待,tij*1,倒数第二样菜会使最后2个人等待,tij*2,这样子我们发现这就是一个可以控制的费用了。我们接下来的考虑就是基于这种倒着加菜的思想。
   我们把每一个厨师都拆成p个点,然后对于时间为i的厨师,向第j样菜连容量为1,费用为 tij*i的边(这是倒数第i样菜,要让点这样菜之后的菜的i个人都等上 tij 分钟),然后源点连每一个时间厨师容量为1费用为0的边,然后菜向汇点连容量为 它所需要的,费用为0的边,然后跑费用流显然就是答案。
   (因为 以上模型跑最小费用最大流满足条件:
      1.每一种菜都满足了。
      2.每一个厨师每一个时间的确只做了一样菜。
      3.每一个厨师每个时刻做每样菜的代价的确是那么多。
      所以算法正确)
    (关于这个还有一个问题就是假如某一个流流向一个厨师i的克隆K版却不流向K-1,怎么破?)
    (想了想,这可能吗....明显流向K的那个食物流向K-1更优....)

    进一步的理解和启发在此:
     http://hi.baidu.com/squarefk/item/8e2f0c9c2101a53b914f4192
     http://tbrtbr.blog.163.com/blog/static/2211431282013588591481/
    那么我们来看看动态加点究竟是怎么回事....= =
    实际上上面也提到了(红色),实际上一个厨师在第K个克隆人未被增广的时候就没有必要增广第K+1个克隆人,所以我们一开始每一个厨师只拆一个点,然后每一次费用流之后对于那个增广了的厨师克隆新的厨师(拆一个新的点,连新的边)可。这样新增加的点最多Q个,然后这样子的点数就是 O(m+q)的,看起来就和谐许多了恩...
    然后就可以AC了。

    这里还有几点细节。
    首先就是如何知道某一次被扩展的是哪个厨师,以及该厨师当前应该被扩展多少次,后者可以用一个数组记录就可以了,初始化都为1,然后前者嘛,我们回溯增广的时候判断编号就可以了。
    然后就是7个点超时(之前测了一次,用别人的程序测测数据范围....)....
    然后发现是回溯的错误,假设是厨师放源点的话,找的点应该是增广路径距离源点最近的点,放汇点则反之。然后就可以AC了。
=============================================

program vijos1726;
const maxm=320000;
      maxn=5000;
type
  edge=record
  u,v,w,c,pre:longint;
  end;

var
  e:array[0..maxm]of edge;
  last,ti,que,low,pre,hash,d:array[0..maxn]of longint;
  v:array[0..maxn]of boolean;
  tot,n,m,tl,num,cost:longint;
  t:array[0..110,0..50]of longint;

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,u,tmp,aug:longint;
begin
  fillchar(d,sizeof(d),1);
  fillchar(que,sizeof(que),0);
  fillchar(v,sizeof(v),false);
  fillchar(low,sizeof(low),0);
  fillchar(pre,sizeof(pre),0);
  low[s]:=maxlongint;
  low[t]:=low[s];
  v[s]:=true;d[s]:=0;
  l:=0;r:=1;
  que[l]:=s;
  while l<>r do
   begin
     u:=que[l];
     tmp:=last[u];
     while tmp<>-1 do
      begin
        if (d[e[tmp].v]>d[u]+e[tmp].c)and(e[tmp].w>0) 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;
              v[e[tmp].v]:=true;
              r:=(r+1)mod maxn;
            end;
         end;
       tmp:=e[tmp].pre;
      end;
     v[u]:=false;
     l:=(l+1)mod maxn;
   end;
  if low[t]=maxlongint then exit(false);
  cost:=cost+low[t]*d[t];
  u:=t;aug:=low[t];
  while u<>s do
   begin
     if e[pre[u]].u=s then tl:=u;
     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:longint;
begin
  read(n,m);
  fillchar(last,sizeof(last),255);
  fillchar(hash,sizeof(hash),0);
  tot:=-1;
  for i:=1 to n do
   begin
     read(j);
     addedge(i+m,maxn,j,0);
   end;
  for i:=1 to n do
   for j:=1 to m do
    begin
      read(t[j][i]);
      addedge(j,i+m,1,t[j][i]);
      hash[j]:=j;
      ti[j]:=1;
    end;
  for i:=1 to m do
    addedge(0,i,1,0);
  num:=n+m;
  cost:=0;
  while spfa(0,maxn) do
   begin
     k:=hash[tl];
     inc(ti[k]);
     inc(num);
     hash[num]:=k;
     addedge(0,num,1,0);
     for i:=1 to n do
      addedge(num,i+m,1,t[k][i]*ti[k]);
   end;
  write(cost);
end;

begin
  init;
end.





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

历史上的今天

评论

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

页脚

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