7
31
2013
1

【BZOJ2424】【HAOI2010】订货【费用流】

很裸的费用流，不过应当注意题目描述有点问题，它是先把所有东西卖出然后再存入仓库。

?
BZOJ2424
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
program p2424;
    const
        max=10000000;
    type
        bian=record
            w,f,point,next:longint;
        end;
    var
        pd:array[0..100] of boolean;
        x:array[1..1000] of longint;
        after,d,u,l,p:array[0..100] of longint;
        b:array[0..1000] of bian;
        len,i,j,m,n,s:longint;
    function min(k1,k2:longint):longint;
        begin
            if k1<k2 then exit(k1) else exit(k2);
        end;
    procedure ade(k1,k2,k3,k4:longint);
        begin
            inc(len);
            b[len].point:=k2;
            b[len].next:=p[k1];
            b[len].w:=k4;
            b[len].f:=k3;
            p[k1]:=len;
        end;
    procedure add(k1,k2,k3,k4:longint);
        begin
            ade(k1,k2,k3,k4);
            ade(k2,k1,0,-k4);
        end;
    function change:longint;
        var
            tot,now,i,j,k:longint;
        begin
            k:=max;
            now:=n;
            while now>0 do begin
                i:=after[now];
                k:=min(k,b[i].f);
                now:=b[i xor 1].point;
            end;
            now:=n; tot:=0;
            while now>0 do begin
                i:=after[now];
                dec(b[i].f,k);
                inc(b[i xor 1].f,k);
                inc(tot,b[i].w*k);
                now:=b[i xor 1].point;
            end;
            exit(tot);
        end;
    function spfa:boolean;
        var
            i,j,now,head:longint;
        begin
            fillchar(x,sizeof(x),0);
            fillchar(pd,sizeof(pd),false);
            fillchar(after,sizeof(after),-1);
            fillchar(l,sizeof(l),$3f);
            head:=1; now:=0; x[1]:=0; pd[0]:=true; l[0]:=0;
            while head>now do begin
                inc(now);
                i:=p[x[now]];
                while i>-1 do begin
                    j:=b[i].point;
                    if (l[j]>l[x[now]]+b[i].w) and (b[i].f>0) then begin
                        l[j]:=l[x[now]]+b[i].w;
                        after[j]:=i;
                        if pd[j]=false then begin
                            inc(head);
                            x[head]:=j;
                            pd[j]:=true;
                        end;
                    end;
                    i:=b[i].next;
                end;
                pd[x[now]]:=false;
            end;
            if after[n]>-1 then exit(true) else exit(false);
        end;
    function dinic:longint;
        var
            i,j,ans:longint;
        begin
            ans:=0;
            while spfa do
                ans:=ans+change;
            exit(ans);
        end;
    begin
        readln(n,m,s);
        for i:=1 to n do
            read(u[i]);
        for i:=1 to n do
            read(d[i]);
        fillchar(p,sizeof(p),-1);
        fillchhar(b,sizeof(b),0);
        len:=-1;
        for i:=1 to n do
            add(0,i,max,d[i]);
        for i:=1 to n-1 do
            add(i,i+1,s,m);
        for i:=1 to n do
            add(i,n+1,u[i],0);
        inc(n);
        writeln(dinic);
    end.
Category: 费用流 | Tags: | Read Count: 1535
Small_feed 评论 (1)
1
[回复]
Avatar_small
model-paper.com 说:
2023年5月19日 18:37

Modelpapers works on giving out better service in different forms and we do not sell or giveaway your personal information other than public info giving out by you. We are very conscious about mail spam and we try to protect every email as much as possible. In certain cases your mail may be exposed to public. model-paper.com


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com