[BZOJ3993][SDOI2015]星际战争 二分答案+最大流



发现攻击时间具有单调性,于是我们可以二分答案.进而不难想到建出网络流图来check当前答案:源点向炮连边,容量是炮的伤害乘以时间,炮和它能打的机器人连边,容量是+INF,机器人和汇点连边,容量是机器人的护甲.跑一遍最大流,如果最大流等于所有机器人的护甲值之和,就说明可以在mid时间内干掉所有机器人.

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 233
#define eps 1e-4
using namespace std;
int head[N],to[N*N],next[N*N],tot=1;
double f[N*N],a[N],b[N];
inline void add(int x,int y,double z)
{
    to[++tot]=y;f[tot]=z;next[tot]=head[x];head[x]=tot;
    to[++tot]=x;f[tot]=0;next[tot]=head[y];head[y]=tot;
}
int n,m,s,t;
bool map[N][N];
int dis[N*N];
queue<int>q;
bool bfs()
{
    while(!q.empty())q.pop();
    memset(dis,-1,sizeof dis);
    q.push(s);dis[s]=0;
    int x,y;
    while(!q.empty())
    {
        x=q.front();q.pop();
        for(int i=head[x];i;i=next[i])if(dis[y=to[i]]<0&&f[i]>eps)
        {
            dis[y]=dis[x]+1;
            if(y==t)return 1;
            q.push(y);
        }
    }
    return 0;
}
double dinic(int x,double flow)
{
    if(x==t)return flow;
    double temp=flow,a;
    for(int i=head[x];i;i=next[i])if(dis[to[i]]==dis[x]+1&&f[i]>0)
    {
        a=dinic(to[i],min(temp,f[i]));
        if(a<eps)dis[to[i]]=-1;
        temp-=a;
        f[i]-=a;f[i^1]+=a;
        if(temp<eps)break;
    }
    return flow-temp;
}
double maxflow()
{
    double re=0;
    while(bfs())re+=dinic(s,999999999);
    return re;
}
double sum=0;
bool check(double mid)
{
    memset(head,0,sizeof head);
    memset(next,0,sizeof next);
    tot=1;
    for(int i=1;i<=m;i++)
    {
        add(s,i,mid*b[i]);
        for(int j=1;j<=n;j++)if(map[i][j])add(i,m+j,999999999);
    }
    for(int j=1;j<=n;j++)add(m+j,t,a[j]);
    return maxflow()+eps>=sum;
}
int main()
{
    cin>>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 x,i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)scanf("%d",&map[i][j]);
    }
    s=0,t=n+m+1;
    double l=0,r=10000;
    int cnt=50;
    while(cnt--)
    {
        double mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid;
    }
    printf("%lf",l);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注