BZOJ 1070+2879

1070

题意很简单就不扯了,关键是建图

因为一个人可能要修好几辆车,所以一个点代表一个人的话似乎怎么连都无法满足条件:

  1. 若从源向每个人连一条容量1费用0的边,这个人还怎么修好几辆车…

  2. 若从源向每个人连一条容量inf费用0的边,而这个人又向好多车各连了一条容量1费用$t_{i,j}$的边,这样就可能造成这个人同时修了好几辆车…

先不考虑好几个人在修车,考虑一个人修好几辆车,对于一个人来说,他在店中还有$i$个人时修车(或修第$n-i+1$辆车)时需要让店里的顾客每人等待$t$的时间,共等待$t*i$的时间

可以将每个人拆成$n$个点,第$i$个点表示这个人在店里还剩$i$个人时修车,这些点全部和每辆车各连一条容量1费用为<店中人数i*每辆车的等待时间t>的边,这样就把所有的修车情况都考虑到了,共$n*m$个点,每个点连了$n$条边

最后从每辆车向汇连一条容量1费用0的边(限制了每辆车只能修一遍),建图完成

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
program bzoj_1070;
var n,m,ans,i,j,k,tot,ss,tt:longint;
time:array[1..60,1..10]of longint;
d,lst,from:array[0..601]of longint;
l:array[1..100000]of record st,ed,f,c,pre:longint; end;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure link(a,b,f,c:longint);
begin
inc(tot);
l[tot].pre:=lst[a];
lst[a]:=tot;
l[tot].st:=a;
l[tot].ed:=b;
l[tot].f:=f;
l[tot].c:=c;
end;
procedure insert(a,b,f,c:longint);
begin
link(a,b,f,c);
link(b,a,0,-c);
end;
function spfa:boolean;
const qs=100000;
var hd,tl,now,t:longint;
q:array[1..qs]of longint;
v:array[0..qs]of boolean;
begin
fillchar(d,sizeof(d),$7f);
fillchar(v,sizeof(v),false);
hd:=0;
tl:=1;
q[1]:=ss;
d[ss]:=0;
while hd<>tl do
begin
inc(hd);
if hd>qs then hd:=1;
now:=q[hd];
t:=lst[now];
while t<>0 do
begin
if (l[t].f>0)and(d[l[t].ed]>d[now]+l[t].c) then
begin
d[l[t].ed]:=d[now]+l[t].c;
from[l[t].ed]:=t;
if not v[l[t].ed] then
begin
v[l[t].ed]:=true;
inc(tl);
if tl>qs then tl:=1;
q[tl]:=l[t].ed;
end;
end;
t:=l[t].pre;
end;
v[now]:=false;
end;
if d[tt]>maxlongint>>1 then exit(false);
exit(true);
end;
procedure flow;
var f,x:longint;
begin
x:=from[tt];
f:=maxlongint;
while x<>0 do
begin
f:=min(f,l[x].f);
x:=from[l[x].st];
end;
x:=from[tt];
while x<>0 do
begin
dec(l[x].f,f);
inc(l[x xor 1].f,f);
inc(ans,l[x].c*f);
x:=from[l[x].st];
end;
end;
begin
readln(m,n);
for i:=1 to n do
for j:=1 to m do read(time[i,j]);
tot:=1;
ss:=0;
tt:=n*m+n+1;
for i:=1 to m*n do insert(ss,i,1,0);
for i:=n*m+1 to n*m+n do insert(i,tt,1,0);
for i:=1 to m do
for j:=1 to n do
for k:=1 to n do
insert((i-1)*n+j,n*m+k,1,time[k,i]*j);
while spfa do flow;
writeln(ans/n:0:2);
end.

2879

这道题思路与1070基本相同,只是数据略大…按照1070的办法根本存不下,所以我们只添加有用的边,任何时刻使每个厨师的所有点中,只有一个点向菜连着边,就是说只考虑每个厨师的下次做菜,这次做完了再连新的,具体实现就是每次流完之后处理一下

这道题还要注意就是,菜的种数是n,但每种菜可能要做好多份,所以一个厨师做菜的最大次数是所有菜的份数和,还有可以不必每份菜向汇连一条容量1费用0的边,可以直接每种菜向汇连一条容量$p_i$费用0的边

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
109
110
111
112
113
114
115
116
program bzoj_2879;
var l:array[1..3200000]of record st,ed,pre,f,c:longint; end;
pp:array[0..40]of longint;
n,m,p,i,j,ans,tot,ss,tt:longint;
t:array[1..40,1..100]of longint;
lst,d,from:array[0..81000]of longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure link(a,b,f,c:longint);
begin
inc(tot);
l[tot].pre:=lst[a];
lst[a]:=tot;
l[tot].st:=a;
l[tot].ed:=b;
l[tot].f:=f;
l[tot].c:=c;
end;
procedure insert(a,b,f,c:longint);
begin
link(a,b,f,c);
link(b,a,0,-c);
end;
function spfa:boolean;
const qs=81000;
var q:array[1..qs]of longint;
v:array[0..qs]of boolean;
hd,tl,now,k:longint;
begin
hd:=0;
tl:=1;
q[1]:=ss;
fillchar(v,sizeof(v),false);
fillchar(d,sizeof(d),$7f);
v[ss]:=true;
d[ss]:=0;
while hd<>tl do
begin
inc(hd);
if hd>qs then hd:=1;
now:=q[hd];
k:=lst[now];
while k<>0 do
begin
if (l[k].f>0)and(d[now]+l[k].c<d[l[k].ed]) then
begin
d[l[k].ed]:=d[now]+l[k].c;
from[l[k].ed]:=k;
if not v[l[k].ed] then
begin
v[l[k].ed]:=true;
inc(tl);
if tl>qs then tl:=1;
q[tl]:=l[k].ed;
end;
end;
k:=l[k].pre;
end;
v[now]:=false;
end;
if d[tt]>maxlongint>>1 then exit(false);
exit(true);
end;
procedure flow;
var x,f,c,pos,cnt:longint;
begin
x:=from[tt];
f:=maxlongint;
while x<>0 do
begin
f:=min(f,l[x].f);
if l[x].st=ss then pos:=l[x].ed;
x:=from[l[x].st];
end;
x:=from[tt];
while x<>0 do
begin
inc(ans,f*l[x].c);
dec(l[x].f,f);
inc(l[x xor 1].f,f);
x:=from[l[x].st];
end;
c:=(pos-1)mod m+1;
cnt:=(pos-1) div m+1;
for x:=1 to n do insert(cnt*m+c,m*p+x,1,t[x,c]*(cnt+1));
end;
begin
readln(n,m);
p:=0;
for i:=1 to n do
begin
read(pp[i]);
inc(p,pp[i]);
end;
for i:=1 to n do
for j:=1 to m do read(t[i,j]);
ss:=0;
tt:=m*p+n+1;
tot:=1;
for i:=1 to p do
for j:=1 to m do insert(ss,(i-1)*m+j,1,0);
for i:=1 to n do insert(m*p+i,tt,pp[i],0);
for i:=1 to m do
for j:=1 to n do insert(i,m*p+j,1,t[j,i]);
ans:=0;
while spfa do flow;
writeln(ans);
end.