题意
\(m\)个人\(n\)个物品，第\(i\)个物品生命值为\(A_i\)，第\(i\)个人每秒可以减少一个物品\(B_i\)的生命值，给出一个\(m \times n\)的矩阵，如果\(i\)行\(j\)列为\(1\)，则表示第\(i\)个人可以攻击第\(j\)个物品，否则不能攻击，问至少需要多少秒，能干掉所有物品。一个物品被干掉当且仅当生命值小于等于\(0\)。（\(n, m \le 50, 1 \le A_i \le 10^5, 1 \le B_i \le 10^3\) ）
分析
我们可以二分时间，然后判定。首先我们能列出一些约束，然后发现可以用上下界可行流来做。
题解
二分时间\(t\)，令\(C(i, j)\)表示第\(i\)个人减少了\(j\)物品的血量，容易列出：
\[\sum_{j} C(i, j) \le t \times B_i
\]
\]
\[\sum_{i} C(i, j) \ge A_j
\]
\]
然后裸上上下界可行流即可。
（即使有\(2500\)个点....
#include <bits/stdc++.h>
using namespace std;
typedef long double lf;
const lf eps=1e-5, oo=1e150;
const int N=55, M=55, nN=3005, nM=nN*8;
inline int dcmp(lf a) {
return a>-eps?a>=eps:-1;
}
int ihead[nN], cnt, A[N], B[M], ed[M][N], n, m;
struct E {
int next, from, to;
lf cap;
}e[nM];
void add(int x, int y, lf cap) {
e[++cnt]=(E){ihead[x], x, y, cap}; ihead[x]=cnt;
e[++cnt]=(E){ihead[y], y, x, 0 }; ihead[y]=cnt;
}
lf isap(int s, int t, int n) {
static int gap[nN], cur[nN], d[nN], p[nN];
memset(gap, 0, sizeof(int)*(n+1));
memset(d, 0, sizeof(int)*(n+1));
memcpy(cur, ihead, sizeof(int)*(n+1));
gap[0]=n;
lf ret=0, f;
for(int i, x=s; d[s]<n; ) {
for(i=cur[x]; i; i=e[i].next) if(dcmp(e[i].cap)>0 && d[x]==d[e[i].to]+1) break;
if(i) {
p[e[i].to]=cur[x]=i; x=e[i].to;
if(x==t) {
for(f=oo; x!=s; x=e[p[x]].from) f=min(f, e[p[x]].cap);
for(x=t; x!=s; x=e[p[x]].from) e[p[x]].cap-=f, e[p[x]^1].cap+=f;
ret+=f;
}
}
else {
if(!--gap[d[x]]) break;
d[x]=n;
cur[x]=ihead[x];
for(i=cur[x]; i; i=e[i].next) if(dcmp(e[i].cap)>0 && d[x]>d[e[i].to]+1) d[x]=d[e[i].to]+1;
++gap[d[x]];
if(x!=s) x=e[p[x]].from;
}
}
return ret;
}
bool check(lf R) {
int in=0, all=n*m+n+m+2+2, s=n*m+n+m+1, t=s+1, S=t+1, T=S+1;
memset(ihead, 0, sizeof(int)*(all+1));
cnt=1;
for(int i=1; i<=m; ++i) {
int idi=n*m+i;
add(s, idi, R*B[i]);
for(int j=1; j<=n; ++j) {
int idj=n*m+m+j;
int id=(i-1)*n+j;
add(idi, id, oo);
if(ed[i][j]) {
add(id, idj, oo);
}
}
}
for(int i=1; i<=n; ++i) {
int id=n*m+m+i;
add(id, T, A[i]);
in+=A[i];
}
add(S, t, in);
add(t, s, oo);
lf sum=isap(S, T, all);
if(dcmp(sum-in)!=0) {
return 0;
}
return 1;
}
int main() {
scanf("%d%d", &n, &m);
for(int i=1; i<=n; ++i) {
scanf("%d", &A[i]);
}
for(int i=1; i<=m; ++i) {
scanf("%d", &B[i]);
}
for(int i=1; i<=m; ++i) {
for(int j=1; j<=n; ++j) {
scanf("%d", &ed[i][j]);
}
}
lf l=0, r=1e6;
while(dcmp(r-l)>0) {
lf mid=(l+r)/2;
if(check(mid)) {
r=mid;
}
else {
l=mid;
}
}
printf("%.9Lf\n", r);
return 0;
}