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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【vijos】【p1621】【终极情报网】  

2014-03-04 18:49:37|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
      题目长题目各种长= =
      先梳理一下题意。
      有N个点及一个起点S,一个终点W,两两之间及每一个点与起点有容量限制和一个概率Pij(pij∈[0.1]),然后N个点到终点无容量限制,概率均为1,然后求 一种流的路径方案,使得∏∏pij 最大,其中第一个∏的每一项表示一条路径, 第二个∏ 是每一条路径的边的概率的乘积,要求满足流的限制条件。
       如果乘积改成加减就好做了....
       当然也不是不能改...
       我们实际上也可以连续最短路原理,即要求 ∏的每一条路径的 ∏pij 都最小,我们想让∏pij最小,能让乘法变成加法那是再好不过的了,乘法变加法.....咱们给这一坨取一个对数,那么∏pij 变成 ∑ log pij ,每一项都小于0,原来要求那个最大,实际上就是要求这个的和最大,咱们不如就改成相反数,那么就是和最小,跑最小费用流就可以了。
       对于咱蒟蒻,此题惊喜的说明了,费用流是可以跑分数的,不知道容量可不可以跑分数...
       最后三个点超时,Spfa优化不能...待写zkw费用流过...
       然后去找了几个zkw准备背模板,提交的时候发现某个裸spfa竟然过了...而它只是加了SLF优化....然后又搞了半天SLF,然后还是超时,正百思不得其解的时候,注意到它松弛时候的条件:
         if (d[e[tmp].v]>d[u]+e[tmp].w+1e-12)
         红字部分加上之后立刻飞快....
        啊啊啊啊,又一次被实数坑了,只要在误差1e-12内都视作相等,不然会程序会无限松弛 某条本来应该相等的。
        坑.....
    
        另外此题的输出也是十分的纠结的,发现可以用变量控制输出小数位数,长姿势了。
=========================================

program vijosp1621;
const maxm=300000;
      maxn=600;
type
  edge=record
  u,v,w,pre:longint;
  c:double;
  end;

var e:array[0..maxm]of edge;
    last,low,pre,am:array[-1..maxn]of longint;
    que:array[0..maxm]of longint;
    ass:array[0..maxn]of double;
    d:array[0..maxn]of double;
    v:array[0..maxn]of boolean;
    tot,max,n,li:longint;
    cost:double;

procedure addedge(u,v,w:longint;c:double);
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 u,tmp,l,r,aug,i:longint;
begin
  fillchar(que,sizeof(que),0);
  fillchar(low,sizeof(low),0);
  fillchar(v,sizeof(v),false);
  fillchar(pre,sizeof(pre),0);
  for i:=0 to n+3 do d[i]:=1e29;
  d[0]:=-1;
  d[s]:=0;v[s]:=true;
  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];
      v[u]:=false;
      l:=(l+1)mod maxm;
      while tmp<>-1 do
       begin
         if (e[tmp].w>0)and(d[e[tmp].v]>d[u]+e[tmp].c+1e-12)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;
    end;
  if low[t]=maxlongint then exit(false);
  cost:=cost+d[t]*low[t];
  max:=max+low[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,u,v:longint;
    w,ans,s:double;
begin
  read(n,li);
  tot:=-1;
  fillchar(last,sizeof(last),255);
  for i:=1 to n do
   read(ass[i]);
  for i:=1 to n do
   read(am[i]);
  for i:=1 to n do
   if am[i]<>0 then
   addedge(n+3,i,am[i],-ln(ass[i]));
  for i:=1 to n do
   begin
     read(j);
     if j=1 then addedge(i,n+1,maxlongint,0.0);
   end;
  read(i,j);
  while (i<>-1)and(j<>-1) do
   begin
     read(w,u);
     addedge(i,j,u,-ln(w));
     addedge(j,i,u,-ln(w));
     read(i,j);
   end;
  cost:=0;
  max:=0;
  addedge(n+2,n+3,li,0.0);
  while spfa(n+2,n+1) do;
  if max<li then cost:=0
  else cost:=exp(-cost);
  w:=1;
  u:=0;
  s:=cost;
  while trunc(s)=0 do
   begin
     w:=w*0.1;
     s:=s*10;
     inc(u);
   end;
  ans:=0;
  for i:=1 to 6 do
   begin
     ans:=ans+w*trunc(s);
     s:=s*10-trunc(s)*10;
     w:=w*0.1;
   end;
  write(ans:0:(u+4));
end;

begin
  assign(input,'agent.in8');reset(input);
  init;
  close(input);
end.


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

历史上的今天

评论

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

页脚

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