题意

\(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 
    
     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]
     
      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;}