容易想到一个网络流模型,就是将武器作为节点放在左边,机器作为节点放在右边,一个武器可以攻击一个机器,就在这个武器和这个机器之间连容量为\(inf\)的边,因为武器可以攻击机器任意多的伤害。

那么如何建立其他边呢?

由于最小时间不好求,我们考虑二分答案\(Time\)(注意这是一个实数),将问题转化为询问可行性,设当前答案区间的中点为\(M\)。

然后我们建立汇点\(t\),机器\(i\)向\(t\)连一条容量为\(A_i\)的边,这条边的流量变为0表示这台机器受到了\(A_i\)的伤害,即被摧毁了;

接下来我们建立源点\(s\),\(s\)向每个武器\(i\)连一条容量为\(B_i\times M\)的边,即它在\(M\)时间内可以造成的总伤害。

我们只需检查这个网络的最大流是否等于\(\sum_{i=1}^nA_i\)即可。

由于需要进行实数比较,记得定义精度。此题建议精度为\(10^{-9}\)到\(10^{-8}\)之间,\(10^{-10}\)太小了会WA掉。

code:

#include
    
     #define REV(x) ((x&1)?x+1:x-1)using namespace std;const double INF=1e9;const double _=1e-9;struct edge{    int t,nxt;    double w;}e[5210];int n,m,a[55],b[55],ch[55][55],t,be[110],cnt,sum,dep[110],vis[110];double l,r,mid,fl[110];queue
     
      q;void add(int x,int y,double v){    e[++cnt].t=y,e[cnt].w=v,e[cnt].nxt=be[x],be[x]=cnt;}bool eq(double x,double y){    return abs(x-y)<=_;}void Build(double tim){    cnt=0,memset(be,0,sizeof(be));    for(int i=1;i<=n;i++)add(m+i,n+m+1,a[i]),add(n+m+1,m+i,0);    for(int i=1;i<=m;i++)add(0,i,b[i]*tim),add(i,0,0.0);    for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)ch[i][j]?add(i,m+j,INF),add(m+j,i,0),0:0;}bool Getd(int x){    memset(dep,0,sizeof(dep));    q.push(x),dep[x]=1;    int tg=0;    while(!q.empty()){        t=q.front(),q.pop(),tg++;        for(int i=be[t];i;i=e[i].nxt)(!eq(e[i].w,0)&&!dep[e[i].t])?q.push(e[i].t),dep[e[i].t]=dep[t]+1:0;    }    return dep[n+m+1];}void Upd(int ei,double fl){    e[ei].w-=fl,e[REV(ei)].w+=fl;}double dfs(int x,double nf){    if(x==n+m+1)return nf;    vis[x]=1;    double af,tf=0;    for(int i=be[x];!eq(nf,0.0)&&i;i=e[i].nxt){        (!eq(e[i].w,0.0)&&!vis[e[i].t]&&dep[e[i].t]==dep[x]+1)?af=dfs(e[i].t,min(nf,e[i].w)),Upd(i,af),nf-=af,tf+=af:0;    }    return vis[x]=0,tf;}double Dinic(){    double tot=0;    while(Getd(0))tot+=dfs(0,INF);    return tot;}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;++i)scanf("%d",&a[i]),sum+=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",&ch[i][j]);    Build(0);    Getd(0);    r=sum;    for(int fr=1;fr<=200;++fr){        mid=(l+r)/2.0;        Build(mid);        eq(Dinic(),sum)?r=mid:l=mid;    }    printf("%.10lf",l);    return 0;}