BZOJ

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.