[文章目录]
Description
给你m个炮台，对于时间t，可以造成t*bi的伤害。有n个目标需要攻击，有ai的血量。炮台可以同时攻击，并给出了每个炮台可攻击的目标集合，询问最小的时间使得目标的血量都降为0.
二分+网络流
二分时间，然后s向每个炮台连边，流量为t*bi，然后每个炮台和自己的可及目标连边，流量为inf，每个目标向汇点连边。如果最大流等于总伤害，说明t时间可以完成，反之不行。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,s,t;
const double inf=10000000;
double a[60],b[60],sum;
int head[110],to[10000],nxt[10000],cnt=1;
double f[10000];
void add(int x,int y,int z)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
f[cnt]=z;
to[++cnt]=x;
nxt[cnt]=head[y];
head[y]=cnt;
f[cnt]=0;
}
int dis[110];
queue<int>q;
bool bfs()
{
while(!q.empty()) q.pop();
memset(dis,-1,sizeof dis);
dis[s]=0; q.push(s);int x;
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[to[i]]<0)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
double dinic(int x,double flow)
{
if(x==t) return flow;
double xx,tmp=flow;
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(f[i],tmp));
if(xx<1e-7) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(tmp<1e-7) break;
}
return flow-tmp;
}
bool check(double x)
{
for(int i=2;i<=cnt;i+=2)
f[i]+=f[i^1],f[i^1]=0;
double ans=0;
for(int i=head[s];i;i=nxt[i])
{
f[i^1]=0;
f[i]=x*b[to[i]];
}
while(bfs()) ans+=dinic(s,inf);
return sum-ans<=1e-7;
}
int main()
{
scanf("%d%d",&n,&m);
s=n+m+1;t=s+1;
for(int i=1;i<=n;i++) scanf("%lf",&a[i]),sum+=a[i];
for(int i=1;i<=m;i++) scanf("%lf",&b[i]);
for(int i=1;i<=n;i++) add(i+m,t,a[i]);
for(int i=1;i<=m;i++) add(s,i,0);
int x;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&x);
if(x) add(i,m+j,inf);
}
}
double l=0,r=6000000,mid;
while(r-l>1e-7)
{
mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid;
}
printf("%.6lf",r);
return 0;
}