[BZOJ3993/Luogu3324][SDOI2015]星际战争(网络流,二分)

发布于 2018-02-07  75 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3993/Luogu3324][SDOI2015]星际战争(网络流,二分)

Description

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

Http

BZOJ
Luogu

Tag

网络流,二分

解决思路

二分需要多少时间,转化成判定型问题。
网络流建模,从源点连到激光武器容量为这段时间武器总共的攻击输出(没错你没有看错容量是实数),从巨型机器人连到汇点连机器人的血量。求最大流看是否与血量之和相等。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

#define ll long long
#define ld long double
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=120;
const int maxM=maxN/2*maxN/2*10;
const ld eps=1e-5;
const int inf=500000;

class Edge
{
public:
    int v;ld flow;
};

int n,m,S,T;
int A[maxN],B[maxN];
int sumA;
int Atta[51][51];
int edgecnt=-1,Head[maxN],Next[maxM];
Edge E[maxM];
int Depth[maxN],Queue[maxN],cur[maxN];

void Add_Edge(int u,int v,ld flow);
bool Check(ld tim);
bool Bfs();
ld dfs(int u,ld flow);

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&A[i]),sumA+=A[i];
    for (int i=1;i<=m;i++) scanf("%d",&B[i]);
    S=n+m+1;T=n+m+2;
    for (int i=1;i<=m;i++) for (int j=1;j<=n;j++) scanf("%d",&Atta[i][j]);
    ld l=0,r=50100;
    ld Ans=0;
    do
    {
        ld mid=(l+r)/(ld)2;
        if (Check(mid)) Ans=mid,r=mid-eps;
        else l=mid+eps;
    }
    while (fabs(r-l)>=eps);
    printf("%.6LF\n",Ans);
    return 0;
}

void Add_Edge(int u,int v,ld flow)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;E[edgecnt].v=v;E[edgecnt].flow=flow;
    edgecnt++;Next[edgecnt]=Head[v];Head[v]=edgecnt;E[edgecnt].v=u;E[edgecnt].flow=0;
    return;
}

bool Check(ld tim)//二分判定
{
    edgecnt=-1;mem(Head,-1);
    for (int i=1;i<=n;i++) Add_Edge(i+m,T,(ld)A[i]);
    for (int i=1;i<=m;i++) Add_Edge(S,i,(ld)B[i]*tim);
    for (int i=1;i<=m;i++) for (int j=1;j<=n;j++) if (Atta[i][j]) Add_Edge(i,j+m,inf);
    ld mxflow=0;
    while (Bfs())
    {
        for (int i=1;i<=T;i++) cur[i]=Head[i];
        while (1)
        {
            ld di=dfs(S,inf);
            mxflow+=di;
            if (fabs(di)<=eps) break;
        }
    }
    if (fabs(mxflow-sumA)<=eps) return 1;
    return 0;
}

bool Bfs()
{
    mem(Depth,-1);
    int h=1,t=0;Queue[1]=S;Depth[S]=1;
    do
    {
        int u=Queue[++t];
        for (int i=Head[u];i!=-1;i=Next[i])
        {
            if ((fabs(E[i].flow)>=eps)&&(Depth[E[i].v]==-1))
                Depth[Queue[++h]=E[i].v]=Depth[u]+1;
        }
    }
    while (h!=t);
    if (Depth[T]==-1) return 0;
    return 1;
}

ld dfs(int u,ld flow)
{
    if (u==T) return flow;
    for (int &i=cur[u];i!=-1;i=Next[i])
        if ((Depth[E[i].v]==Depth[u]+1)&&(fabs(E[i].flow)>eps))
        {
            ld di=dfs(E[i].v,min(flow,E[i].flow));
            if (fabs(di)>eps)
            {
                E[i].flow-=di;
                E[i^1].flow+=di;
                return di;
            }
        }
    return 0;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3993/Luogu3324][SDOI2015]星际战争(网络流,二分)


HNCJ OIer 一枚