【BZOJ3993】 星际战争

时间：2022-02-07 15:52:45

Time Limit: 1000 ms   Memory Limit: 128 MB

Description

　　 3333年，在银河系的某星球上，X军团和Y军团正在激烈地作战。在战斗的某一阶段，Y军团一共派遣了N个巨型机器人进攻X军团的阵地，其中第i个巨型机器人的装甲值为Ai。当一个巨型机器人的装甲值减少到0或者以下时，这个巨型机器人就被摧毁了。X军团有M个激光武器，其中第i个激光武器每秒可以削减一个巨型机器人Bi的装甲值。激光武器的攻击是连续的。这种激光武器非常奇怪，一个激光武器只能攻击一些特定的敌人。Y军团看到自己的巨型机器人被X军团一个一个消灭，他们急需下达更多的指令。为了这个目标，Y军团需要知道X军团最少需要用多长时间才能将Y军团的所有巨型机器人摧毁。但是他们不会计算这个问题，因此向你求助。

Input

　　第一行，两个整数，N、M。

　　第二行，N个整数，A1、A2…AN。
　　第三行，M个整数，B1、B2…BM。
　　接下来的M行，每行N个整数，这些整数均为0或者1。这部分中的第i行的第j个整数为0表示第i个激光武器不可以攻击第j个巨型机器人，为1表示第i个激光武器可以攻击第j个巨型机器人。

Output

　　 一行，一个实数，表示X军团要摧毁Y军团的所有巨型机器人最少需要的时间。输出结果与标准答案的绝对误差不超过10-3即视为正确。

Sample Input

　　2 2
　　3 10
　　4 6
　　0 1
　　1 1

Sample Output

　　1.300000

HINT

　　【样例说明1】

　　战斗开始后的前0.5秒，激光武器1攻击2号巨型机器人，激光武器2攻击1号巨型机器人。1号巨型机器人被完全摧毁，2号巨型机器人还剩余8的装甲值；

　　

　　接下来的0.8秒，激光武器1、2同时攻击2号巨型机器人。2号巨型机器人被完全摧毁。
　　对于全部的数据，1<=N, M<=50，1<=Ai<=105，1<=Bi<=1000，输入数据保证X军团一定能摧毁Y军团的所有巨型机器人
 

Solution

　　如果答案是$t$，那么最大流的连边方法是：源点向每一门炮$i$连一条容量$B_i*t$的边，炮向对应机器人连容量正无穷的边，机器人向汇点连容量$A_i$的边。

　　这个模型的关键在于，如果时间$t$定下来，即每一门炮的输出量固定，那么只需用最大流分配一次，看一看每一个机器人是否被流满所需值$A_i$，即最大流是不是$\sum A_i$，就可以判断这一个时间内满不满足要求。因为如果最大流是$\sum A_i$，必定存在一种激光炮的合作方案能在$t$内消灭机器人。

　　那么直接对$t$二分答案来跑最大流就好啦。

　　记得用$eps$判断。

#include <cstdio>

#include <queue>

using namespace std;

const double INF=1e10,eps=1e-;

int n,m,all,S,T,can[][],a[],b[],sum;

int h[],tot;

int dis[],cur[];

struct Edge{int v,next;double f;}g[];

queue<int> q;

inline double min(double x,double y){return x<y?x:y;}

inline double abs(double x){return x<?-x:x;}

inline void addEdge(int u,int v,double f){

    g[++tot].v=v; g[tot].f=f; g[tot].next=h[u]; h[u]=tot;

    g[++tot].v=u; g[tot].f=; g[tot].next=h[v]; h[v]=tot;

}

bool bfs(){

    while(!q.empty()) q.pop();

    q.push(S);

    for(int i=;i<=all;i++) dis[i]=-;

    dis[S]=;

    while(!q.empty()){

        int u=q.front(); q.pop();

        for(int i=h[u],v;i;i=g[i].next)

            if(g[i].f>eps&&dis[v=g[i].v]==-){

                dis[v]=dis[u]+;

                if(v==T) return true;

                q.push(v);

            }

    }

    return dis[T]!=-;

}

double dfs(int u,double delta){

    if(u==T) return delta;

    double get,ret=;

    for(int i=cur[u],v;i&&delta>eps;i=g[i].next)

        if(g[i].f>eps&&dis[v=g[i].v]==dis[u]+){

            get=dfs(v,min(delta,g[i].f));

            g[i].f-=get;

            g[i^].f+=get;

            if(g[i].f>eps) cur[u]=i;

            delta-=get;

            ret+=get;

        }

    if(ret<eps) dis[u]=-;

    return ret;

}

double dinic(){

    double ret=;

    while(bfs()){

        for(int i=;i<=all;i++) cur[i]=h[i];

        ret+=dfs(S,INF);

    }

    return ret;

}

void buildGraph(double t){

    tot=;

    for(int i=;i<=all;i++) h[i]=;

    for(int i=;i<=m;i++)

        addEdge(S,i,t*b[i]);

    for(int i=;i<=m;i++)

        for(int j=;j<=n;j++)

            if(can[i][j])

                addEdge(i,m+j,INF);

    for(int i=;i<=n;i++)

        addEdge(m+i,T,a[i]);

}

int main(){

    scanf("%d%d",&n,&m);

    all=n+m+; S=n+m+; T=n+m+;

    for(int i=;i<=n;i++) scanf("%d",&a[i]),sum+=a[i];

    for(int i=;i<=m;i++) scanf("%d",&b[i]);

    for(int i=;i<=m;i++)

        for(int j=;j<=n;j++) scanf("%d",&can[i][j]);

    double l=,r=,mid,ans;

    while(l+eps<r){

        mid=(l+r)/;

        buildGraph(mid);

        ans=dinic();

        if(abs(sum-ans)<eps) r=mid;

        else l=mid;

    }

    printf("%.8lf\n",l);

    return ;

}

奇妙代码

 
 

相关文章