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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1070】【SCOI2007】【修车】  

2014-03-24 20:15:53|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   题目大意:M个修车的N个送车修的,一次只能修一辆车,然后要求安排M个修车人修那些车及其修车顺序,使得每位顾客的平均等待时间最短。
   这道题有一种做过的即视感233,VijosP1726美食节
   咱们考虑倒着顺序给每一个修车的加车,也就是说先后给修车的加了 i,j,k,l 四辆车,那么他修车的顺序就应该是 l,k,j,i 。
   容易发现,这个无后效性,每一辆车的贡献=这辆车的修理时间x到这辆为止总共加的车。现在就按vijos的那种方法动态加点跑最小费用流即可。
   还是来复习一下怎么做把。
   首先给源点向顾客连容量为1的边,然后将技术人员和汇点连容量为1的边,然后顾客和技术人员之间连容量为1的,费用为Tij的边(Tij就是第j个技术人员修第i辆车的时间),然后跑一次最小费用流,就找到修车的那个技术人员,然后新建一个节点,这次的费用为Tij*2,然后继续跑最小费用。这样子下去就可以AC了。
   PS:一开始脑抽了把最大的点数开成10,WA一次
===========================================

program bzoj1070;
const maxm=100000;
      maxn=10000;
type edge=record
     u,v,w,c,pre:longint;
     end;

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

function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
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 spfa(s,t:longint):boolean;
var u,tmp,l,r,aug:longint;
begin
  fillchar(que,sizeof(que),0);
  fillchar(pre,sizeof(pre),0);
  fillchar(d,sizeof(d),1);
  fillchar(v,sizeof(v),false);
  v[s]:=true;low[s]:=maxlongint;
  low[t]:=low[s];
  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 (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;
           pre[e[tmp].v]:=tmp;
           low[e[tmp].v]:=min(low[u],e[tmp].w);
           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);
  los:=e[pre[t]].u;
  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,sum:longint;
    ans:double;
begin
  read(m,n);
  tot:=-1;cost:=0;
  fillchar(last,sizeof(last),255);
  for i:=1 to n do
    addedge(0,i,1,0);
  for i:=1 to m do
    addedge(i+n,maxn,1,0);
  for i:=1 to n do
   for j:=1 to m do
    begin
     read(t[i][j]);
     addedge(i,j+n,1,t[i][j]);
    end;
  fillchar(hash,sizeof(hash),0);
  fillchar(num,sizeof(num),0);
  for i:=1 to m do
   hash[i+n]:=i;
  for i:=1 to m do
   num[i]:=1;
  sum:=n+m;
  while spfa(0,maxn) do
   begin
     inc(sum);
     k:=hash[los];
     hash[sum]:=k;
     inc(num[k]);
     for i:=1 to n do
       addedge(i,sum,1,t[i][k]*num[k]);
     addedge(sum,maxn,1,0);
   end;
  ans:=cost/n;
  write(ans:0:2);
end;

begin
  init;
end.





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

历史上的今天

评论

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

页脚

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