bzoj 3993: [SDOI2015]星际战争

.

题意：m个激光武器打n个机器人，问最快多久打完。
题解：二分+网络流。流量表示输出的伤害。
代码：

#include<bits/stdc++.h>
using namespace std;

int n,m,num,fst[110],s,t,a[60],b[60],c[60][60],sum=0,h[110];
struct edge
{
    int x,y,n;
    double d;
}e[6000];
double inf=1e13,eps=1e-4;

void ins(int x,int y,double d)
{
    e[++num]={x,y,fst[x],d};
    fst[x]=num;
}
void build(double x)
{
    memset(fst,0,sizeof(fst));
    num=1;
    for(int i=1;i<=n;i++)
    {
        ins(i+m,t,a[i]);
        ins(t,i+m,0);
    }
    for(int i=1;i<=m;i++)
    {
        ins(s,i,x*b[i]);
        ins(i,s,0);
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(c[i][j])
            {
                ins(i,j+m,inf);
                ins(j+m,i,0);
            }
        }
    }
}
bool bh()
{
    static queue<int>q;
    memset(h,0,sizeof(h));
    q.push(s);
    h[s]=1;
    while(!q.empty())
    {
        int x=q.front();
        for(int i=fst[x];i;i=e[i].n)
        {
            int y=e[i].y;
            if(!h[y]&&e[i].d)
            {
                h[y]=h[x]+1;
                q.push(y);
            }
        }
        q.pop();
    }
    return h[t];
}
double fd(int x,double f)
{
    if(x==t)
    return f;
    double s=0;
    for(int i=fst[x];i;i=e[i].n)
    {
        int y=e[i].y;
        if(h[y]==h[x]+1&&e[i].d>eps&&f>s)
        {
            double t=fd(y,min(e[i].d,f-s));
            e[i].d-=t;
            e[i^1].d+=t;
            s+=t;
        }
    }
    return s;
}
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",&c[i][j]);
    double l=0,r=5000000;
    s=0;
    t=n+m+1;
    while(l+eps<r)
    {
        double md=(l+r)/2;
//        printf("%g %g %g\n",l,r,md);
        build(md);/*
        for(int i=2;i<=num;i+=2)
        {
            printf("%d %d %g\n",e[i].x,e[i].y,e[i].d);
        }*/
        double ss=0;
        while(bh())
        ss+=fd(s,inf);
        if(ss>=sum)
        r=md;
        else
        l=md;
    }
    printf("%lf",l);
}