看了标签恍然大悟
我们可以二分所用的时间(t)，然后对于每一个武器，从源点向它们连长度为伤害( imes t)的边，然后武器向它们能攻击的敌人连长度为(inf)的边，对于每个敌人，向汇点连长度为它们血量的边
然后跑最大流即可
因为要至少保留(2)位小数，为了便于处理，将所有生命和时间都乘了(10000)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define LL long long
#define inf 2147483647777777ll
using namespace std;
LL read() {
LL k = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
k = k * 10 + c - 48, c = getchar();
}
return k * f;
}
struct zzz {
int t, nex; LL len;
}e[10010 << 1]; int head[210], tot = 1;
void add(int x, int y, LL z) {
e[++tot].t = y;
e[tot].len = z;
e[tot].nex = head[x];
head[x] = tot;
}
int s, t, vis[210];
bool bfs() {
queue <int> q; q.push(s);
memset(vis, 0, sizeof(vis)); vis[s] = 1;
while(!q.empty()) {
int k = q.front(); q.pop();
for(int i = head[k]; i; i = e[i].nex) {
if(!vis[e[i].t] && e[i].len) {
vis[e[i].t] = vis[k] + 1, q.push(e[i].t);
if(e[i].t == t) return 1;
}
}
}
return vis[t];
}
LL dfs(int x, LL flow) {
if(!flow|| x == t) return flow;
LL rest = 0, fl;
for(int i = head[x]; i; i = e[i].nex) {
if(vis[e[i].t] == vis[x] + 1 && (fl = dfs(e[i].t, min(e[i].len, flow - rest)))) {
rest += fl; e[i].len -= fl; e[i ^ 1].len += fl;
if(rest == flow) return rest;
}
}
if(rest < flow) vis[x] = 0;
return rest;
}
LL dinic() {
LL ans = 0;
while(bfs()) ans += dfs(s, 2147483647777777ll);
return ans;
}
LL a[210], b[210], k; bool ff[210][210];
int main() {
int n = read(), m = read(); s = 0, t = n+m+1;
for(int i = 1; i <= n; ++i) a[i] = read() * 10000, k += a[i];
for(int i = 1; i <= m; ++i) b[i] = read();
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j)
ff[i][j] = read();
LL l = 0, r = 100000000000ll;
while(l < r) {
LL mid = (l + r) >> 1;
tot = 1; memset(head, 0, sizeof(head));
for(int i = 1; i <= n; ++i)
add(m+i, t, a[i]), add(t, m+i, 0);
for(int i = 1; i <= m; ++i)
add(s, i, b[i] * mid), add(i, s, 0);
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j)
if(ff[i][j]) add(i, m+j, inf), add(m+j, i, 0);
LL x = dinic();
if(x < k) l = mid + 1;
else r = mid;
}
printf("%lf", (double)l/10000);
return 0;
}