博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
bzoj 1221 软件开发 费用流
阅读量:5728 次
发布时间:2019-06-18

本文共 3897 字,大约阅读时间需要 12 分钟。

应该比较好看出来是费用流,那么就考虑怎么构图

首先我们把一天拆成两个点,XI,YI,分别代表这一天买了多少

和洗多少,再加入源和汇S,T

1.每一天我们可以买新的毛巾,所以连接一条从S到XI的边,流量为正无穷(因为可以买好多),费用为f

2.然后我们对于买来的毛巾可以洗,每天都产生need[i]的毛巾可以洗,那么连一条从S到YI的边,

流量为need[i],费用为0(因为只决定要洗,没有确定洗的方案,所以先不算费用)

3.每一条要用a方法洗的毛巾,我们连一条从YI到X(I+a+1)的边,流量为正无穷(下文解释),费用为fa的

4.每一条要用b方法洗的毛巾,我们连一条从YI到X(I+b+1)的边,流量为正无穷(下文解释),费用为fb的

5.因为每天剩下的毛巾,我们可以不当天洗,所以连接一条从YI到Y(I+1)的边,流量为正无穷,费用为0(所以每天可以洗

的毛巾的个数是可能会很多的,4,5建的边流量要是正无穷)

6.那么我们每天买的毛巾除了洗,还可以不洗,也就是直接扔掉,所以连一条XI到T的边,流量为need[i],费用为0

/**************************************************************    Problem: 1221    User: BLADEVIL    Language: Pascal    Result: Accepted    Time:1952 ms    Memory:8120 kb****************************************************************/ //By BLADEVILvar    n, a, b, f, fa, fb  :longint;    need                :array[0..1010] of longint;    pre, other,len      :array[0..500010] of longint;    cost                :array[0..500010] of longint;    last                :array[0..4010] of longint;    ss, tt              :longint;    que                 :array[0..5000] of longint;    dis                 :array[0..5000] of longint;    flag                :array[0..5000] of boolean;    father              :array[0..5000] of longint;    ans                 :int64;    l                   :longint;      function min(a,b:longint):longint;begin    if a>b then min:=b else min:=a;end;      procedure connect(a,b,c,d:longint);begin    inc(l);    pre[l]:=last[a];    last[a]:=l;    other[l]:=b;    len[l]:=c;    cost[l]:=d;end;      procedure init;var    i                   :longint;    use                 :longint;begin    read(n,a,b,f,fa,fb);    for i:=1 to n do read(need[i]);    l:=1;    ss:=2*n+1;    tt:=2*n+2;    for i:=1 to n do    begin        connect(ss,2*i-1,maxlongint,f);        connect(2*i-1,ss,0,-f);        connect(2*i-1,tt,need[i],0);        connect(tt,2*i-1,0,0);        connect(ss,2*i,need[i],0);        connect(2*i,ss,0,0);        use:=i+a+1;        if use<=n then        begin            use:=use*2-1;            connect(2*i,use,maxlongint,fa);            connect(use,2*i,0,-fa);        end;        use:=i+b+1;        if use<=n then        begin            use:=use*2-1;            connect(2*i,use,maxlongint,fb);            connect(use,2*i,0,-fb);        end;    end;    for i:=1 to n-1 do    begin        connect(2*i,2*i+2,maxlongint,0);        connect(2*i+2,2*i,0,0);    end;end;  function spfa:boolean;var    q, p, cur               :longint;    h, t                    :longint;begin    filldword(dis,sizeof(dis) div 4,maxlongint div 10);    que[1]:=ss;    dis[ss]:=0;    h:=0; t:=1;    while t<>h do    begin        h:=h mod 5000+1;        cur:=que[h];        flag[cur]:=false;        q:=last[cur];        while q<>0 do        begin            p:=other[q];            if len[q]>0 then            begin                if dis[p]>dis[cur]+cost[q] then                begin                    father[p]:=q;                    dis[p]:=dis[cur]+cost[q];                    if not flag[p] then                    begin                        t:=t mod 5000+1;                        que[t]:=p;                        flag[p]:=true;                    end;                end;            end;            q:=pre[q];        end;    end;    if dis[tt]=maxlongint div 10 then exit(false) else exit(true);end;  procedure update;var    cur                     :longint;    low                     :longint;   begin    low:=maxlongint div 10;    cur:=tt;    while cur<>ss do    begin        low:=min(low,len[father[cur]]);        cur:=other[father[cur] xor 1];    end;    cur:=tt;    while cur<>ss do    begin        dec(len[father[cur]],low);        inc(len[father[cur] xor 1],low);        inc(ans,low*cost[father[cur]]);        cur:=other[father[cur] xor 1];     end;end;  procedure main;begin    while spfa do update;    writeln(ans);end;  begin    init;    main;end.

 

转载于:https://www.cnblogs.com/BLADEVIL/p/3470508.html

你可能感兴趣的文章
深圳联通特邀湖北籍企业参观公司总部大楼举行
查看>>
告警系统主脚本、告警系统配置文件、告警系统监控项目
查看>>
Python 和 PyCharm 在 windows10 环境的安装和设置
查看>>
B-树,B+树与B*树的优缺点比较
查看>>
C语言入门基础之数组——数学和编程的完美结合(图)
查看>>
《远见》的读后感作文1000字范文
查看>>
重置密码、单用户模式、救援模式
查看>>
LAMP环境搭建1-mysql5.5
查看>>
第三课 Linux目录及文件管理、用户组管理及bash重定向
查看>>
shell 脚本攻略--小试牛刀
查看>>
spring boot view override
查看>>
bzoj 2282: [Sdoi2011]消防
查看>>
我的友情链接
查看>>
centos5.9使用RPM包搭建lamp平台
查看>>
关于C#面向对象2
查看>>
Javascript String类的属性及方法
查看>>
vim编辑器如何添加或删除多行注释
查看>>
[LeetCode] Merge Intervals
查看>>
iOS开发-按钮的基本使用
查看>>
在QT和SDL搭建的框架中使用OPENGL在SDL窗口上进行绘图
查看>>