题解：P3324 [SDOI2015] 星际战争

· · 题解

很好的二分练手题。

题意

给定 n 个机器人，装甲为 A_i。m 个武器，每秒可打掉 B_i 的装甲，武器的攻击是连续的。武器 i 只能打指定的机器人 j。求打掉这 m 个机器人的所有装甲的最小时间。

建图

如果不存在时间，此题就是板子。

只需建源点 s 和汇点 t，源点 s 与每个武器连边，边权为 B_i。汇点 r 与每个机器人连边，边权为 A_i。然后如果武器 i 能打到机器人 j，就连 i 向 j 的边，边权为无穷大。

但如果加上时间呢？

这就需要二分了。

我们二分时间（由于时间是实数，我们使用实数二分）。汇点 t 与机器人的连边和武器与机器人的连边与上面一致，重点是源点 s 与武器的连边。

想一想，没有时间时，武器只能打机器人 B_i 的伤害，但由于时间的加入，武器的伤害是不是变成了 time\times B_i。

建图毕。

代码

:::success[Code]

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=1e5+10;
const double inf=1e18;
const double eps=1e-6;
int n,m,s,t;
double maxm=-inf,T,sum;
double ans;
struct node{
    int to,next;
    double w;
}e[2*maxn];
int head[maxn],tot=1;
int a[maxn],b[maxn];
int u[maxn],v[maxn],cnt;
void add(int u,int v,double w){
    e[++tot].to=v;
    e[tot].next=head[u];
    e[tot].w=w;
    head[u]=tot;
}
int dep[maxn],cur[maxn];
bool bfs(){
    queue<int> q;
    memset(dep,-1,sizeof(dep));
    dep[s]=0; q.push(s);
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dep[v]==-1&&e[i].w>eps){
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    return dep[t]!=-1;
}
double dfs(int u,double flow){
    if(u==t) return flow;
    double used=0;
    for(int i=cur[u];i;i=e[i].next){
        cur[u]=i; 
        int v=e[i].to;
        if(dep[v]==dep[u]+1&&e[i].w>eps){
            double rlow=dfs(v,min(flow-used,e[i].w));
            if(rlow>eps){
                e[i].w-=rlow; e[i^1].w+=rlow;
                used+=rlow;
                if(fabs(flow-used)<eps) break;
            }
        }
    }
    return used;
}
double dinic(){
    double ans=0;
    while(bfs()){
        memcpy(cur,head,sizeof(cur));
        ans+=dfs(s,inf);
    }
    return ans;
}
void reset(double mid){
    memset(head,0,sizeof(head)); tot=1;
    for(int i=1;i<=n;i++) add(i+m,t,a[i]),add(t,i+m,0);
    for(int i=1;i<=m;i++) add(s,i,b[i]*mid),add(i,s,0);
    for(int i=1;i<=cnt;i++) add(u[i],v[i],inf),add(v[i],u[i],0);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m; s=0,t=n+m+1;
    for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            int x;
            cin>>x;
            if(x) u[++cnt]=i,v[cnt]=j+m;
        }
    }
    double l=0,r=1e9;
    while(r-l>=eps){
        double mid=(l+r)/2;
        reset(mid);
        if(dinic()==sum){
            ans=mid;
            r=mid;
        }
        else l=mid;
    }
    printf("%.6lf",ans);
    return 0;
}

:::