【20170706】保卫萝卜

题目描述

一群怪物正向着你的萝卜出发……

这群怪物共有N只，第i只怪物的HP为Ai，当怪物的HP减少到0时，这个怪物就被摧毁了。现在你有M座防御塔，其中第i个防御塔每秒可以减少一只怪物Bi点的HP。由于怪物有不同的属性，所以某些怪物会对某些防御塔免疫。

你的任务是计算至少需要多少时间才能消灭所有的怪物。

输入

第一行两个正整数N，M

第二行N个正整数，表示A1~An

第三行M个正整数，表示B1~Bn

接下来是一个M*N的矩阵，矩阵中每个元素均为0或1。第i行第j列为1表示第i座防御塔可以攻击第j只怪物，为0表示第j只怪物对第i座防御塔的攻击免疫。

输出

一行，一个实数，表示所需的最小时间。保留3位小数

1.二分答案

2.网络流check：S向每个塔连时间乘b[i]的边，塔向能够伤害的怪物连INF的边，怪物向T连a[i]的边，跑一遍最大流，看是否等于所有a[i]的总和；

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define INF 0x7fffffff
#define MN 50
#define T 101
#define S 0
#define eps 1e-5
using namespace std;
int n,m;
double a[MN+5],b[MN+5],sum=0;
bool ifcan[MN+5][MN+5];
int cnt,top;
int head[T+5],d[T+5],q[T*3+5];
struct edge{int t,nex;double w;}e[MN*MN*2+MN*5];
void ins(int f,int t,double w){
    e[++cnt].t=t; e[cnt].nex=head[f]; e[cnt].w=w; head[f]=cnt;
    e[++cnt].t=f; e[cnt].nex=head[t]; e[cnt].w=0; head[t]=cnt;
}
double dfs(int x,double f){
    if(x==T) return f;
    double used=0;
    for(int i=head[x];i;i=e[i].nex)
        if(e[i].w&&d[e[i].t]==d[x]+1){
            double w=dfs(e[i].t,min(f-used,e[i].w));
            used+=w;e[i].w-=w;e[i^1].w+=w;
            if(abs(f-used)<eps) return f;    
        }
    return d[x]=-1,used;
}
bool bfs(){
    memset(d,0,sizeof(d));int i,j;
    for(d[q[top=i=1]=S]=1;i<=top;++i){
        for(int j=head[q[i]];j;j=e[j].nex)
            if(e[j].w&&!d[e[j].t])
                d[q[++top]=e[j].t]=d[q[i]]+1;
    }
    return d[T];
}
bool solve(double t){
    cnt=1;
    double ans=0.0;
    memset(head,0,sizeof(head));
    for(int i=1;i<=T;i++) head[i]=0;
    for(int i=1;i<=m;i++) ins(S,i,b[i]*t);
    for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) if(ifcan[i][j]) ins(i,j+50,INF);
    for(int i=1;i<=n;i++) ins(i+50,T,a[i]);
    while(bfs()) ans+=dfs(S,INF);
    if(abs(ans-sum)<eps) return 1;
    return 0;
}
int main(){
    scanf("%d%d",&n,&m);
    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<=m;i++) for(int j=1;j<=n;j++) cin>>ifcan[i][j];
    double l=0.0,r=5000000.0;
    while(l+eps<r){
        double mid=(l+r)/2;
        if(solve(mid)) r=mid;
        else l=mid;
    }
    printf("%.3lf",l);
    return 0;
} 

————————————————————————————————————

来自Paper Cloud的博客，未经允许，请勿转载，谢谢。