BZOJ

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.