BZOJ 3993

传送门

二分答案,然后网络流验证是否可行

  • 源点向每个武器连容量为时间*攻击力的边
  • 每个武器向能攻击的机器人连容量为攻击力的边
  • 每个机器人向汇点连容量为血量的边

若最大流=总血量则说明当前方案可行

刚开始用的数组直接赋值好慢好慢…所以改成每次重新连


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
117
118
119
120
121
122
123
124
125
126
127
128
program bzoj_3993;
const inf=maxlongint>>1;
qs=5201;
eps=1e-3;
var n,m,i,j,t,ss,tt,tot,tota,len:longint;
l:array[1..5201]of record ed,pre:longint; f:extended; end;
lst:array[1..102]of longint;
a,b:array[1..50]of longint;
lnk:array[1..50,1..50]of boolean;
q,d,seq:array[1..qs]of longint;
ll,rr,mid,maxf:extended;
v:array[1..qs]of boolean;
procedure link(a,b:longint;f:extended);
begin
inc(tot);
l[tot].pre:=lst[a];
lst[a]:=tot;
l[tot].ed:=b;
l[tot].f:=f;
end;
procedure insert(a,b:longint;f:extended);
begin
link(a,b,f);
link(b,a,0);
end;
function bfs:boolean;
var hd,tl,k:longint;
begin
hd:=0;
tl:=1;
for i:=1 to tt do d[i]:=inf;
d[ss]:=0;
q[1]:=ss;
while hd<>tl do
begin
hd:=hd mod qs+1;
k:=lst[q[hd]];
while k<>0 do
begin
if (l[k].f>0)and(d[q[hd]]+1<d[l[k].ed]) then
begin
d[l[k].ed]:=d[q[hd]]+1;
v[l[k].ed]:=true;
tl:=tl mod qs+1;
q[tl]:=l[k].ed;
end;
k:=l[k].pre;
end;
end;
fillchar(v,sizeof(v),false);
exit(d[tt]<inf);
end;
procedure expand;
var i:longint;
f:extended;
begin
f:=inf;
for i:=1 to len do if l[seq[i]].f<f then f:=l[seq[i]].f;
maxf:=maxf+f;
for i:=1 to len do
begin
l[seq[i]].f:=l[seq[i]].f-f;
l[seq[i] xor 1].f:=l[seq[i] xor 1].f+f;
end;
end;
procedure dfs(t:longint);
var k:longint;
begin
v[t]:=true;
if t=tt then
begin
expand;
exit;
end;
k:=lst[t];
while k<>0 do
begin
if (l[k].f>0)and(d[t]+1=d[l[k].ed])and(not v[l[k].ed]) then
begin
inc(len);
seq[len]:=k;
dfs(l[k].ed);
dec(len);
end;
k:=l[k].pre;
end;
end;
begin
readln(n,m);
ss:=n+m+1;
tt:=n+m+2;
tota:=0;
for i:=1 to n do
begin
read(a[i]);
inc(tota,a[i]);
end;
for i:=1 to m do read(b[i]);
for i:=1 to m do
for j:=1 to n do
begin
read(t);
lnk[i,j]:=(t=1);
end;
ll:=0;
rr:=tota;
len:=0;
while ll+eps<rr do
begin
mid:=(ll+rr)/2;
tot:=1;
for i:=1 to n+m+2 do lst[i]:=0;
for i:=1 to m do insert(ss,i,b[i]*mid);
for i:=1 to n do insert(m+i,tt,a[i]);
for i:=1 to m do
for j:=1 to n do if lnk[i,j] then insert(i,m+j,inf);
maxf:=0;
while bfs do dfs(ss);
if maxf+eps>tota then rr:=mid else ll:=mid;
end;
writeln(ll:0:4);
end.