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.
|