Hellc

「题目描述」

3333 年，在银河系的某星球上，X 军团和 Y 军团正在激烈地作战。

在战斗的某一阶段，Y 军团一共派遣了 $N$ 个巨型机器人进攻 $X$ 军 团的阵地。

其中第 $i$ 个巨型机器人的装甲值为$A_i$ ，当一个巨型机器人的装甲值减少到 0 或者以下时，这个巨型机器人就被摧毁了。

X 军团有 $M$ 个激光武器，其中第 $i$ 个激光武器每秒可以削减一个巨型机器人 $B_i$ 的装甲值。

激光武器的攻击是连续的。

这种激光武器非常奇怪，一个激光武器只能攻击一些特定的敌人。

Y 军团看到自己的巨型机器人被 X 军团一个一个消灭，他们急需下达更多的指令。

为了这个目标，Y 军团需要知道 X 军团最少需要用多长时间才能将 Y 军团的所有巨型机器人摧毁。

但是他们不会计算这个问题，因此向你求助。

「题目链接」

BZOJ 3993 星际战争 「SDOI 2015」

「解题思路」

答案显然可以二分，考虑如何判定：对于一个给定的时间，X 的武器能否消灭 Y 所有的机器人。

这种 供应-需求 式问题很适合网络流建图。

从 $S$ 向武器连边，容量为在给定时间内可以供应的伤害，即攻击力乘上时间。

机器人向 $T$ 连边，容量为将其摧毁所需的伤害，即装甲值。

根据攻击关系在 $S$ 和 $T$ 之间连边，容量为 $\infty$ 。

计算最大流，如果等于装甲值总和，则可行。否则不可行。

「AC 代码」

#include <cstdio>
#include <new>
#include <cfloat>
#include <algorithm>
#include <queue>
#include <numeric>
#include <cmath>

const double EPS = 1e-6;

inline int dcmp(double x){
    if(fabs(x) <= EPS) return 0; else return x < 0 ? -1 : 1;
}

inline bool equal(double x, double y){
    return !dcmp(x - y);
}

const int MAX_N = 50;
const int MAX_M = 50;
const int MAX_NODE = MAX_N + MAX_M + 2;
const int MAX_EDGE = 2 * (MAX_N + MAX_N * MAX_M + MAX_M);
 
struct Node{
    struct Edge *e, *cur;
    int d;
} nodes[MAX_NODE];
 
inline Node* node(int i){
    return &nodes[i];
}
 
struct Edge{
    Node *to;
    double cap, res;
    Edge *next, *rev;
 
    Edge() {}
    Edge(Node *fr, Node *to, double cap) : to(to), cap(cap), res(cap), next(fr->e) {}
} edges[MAX_EDGE], *ptr = edges;
 
inline void addEdge(int a, int b, double c){
    Node *u = node(a), *v = node(b);
    u->e = new (ptr++) Edge(u, v, c);
    v->e = new (ptr++) Edge(v, u, 0);
    u->e->rev = v->e, v->e->rev = u->e;
}
 
namespace Dinic{
    int n;
    Node *s, *t;
 
    inline bool bfs(){
        for(Node *v = node(0); v != node(n); v++) v->cur = v->e, v->d = 0;
 
        std::queue<Node*> Q;
        Q.push(s), s->d = 1;
        while(!Q.empty()){
            Node *v = Q.front(); Q.pop();
            for(Edge *e = v->e; e; e = e->next){
                if(dcmp(e->res) > 0 && !e->to->d){
                    e->to->d = v->d + 1;
                    if(e->to == t) return true; else Q.push(e->to);
                }
            }
        }
 
        return false;
    }
 
    inline double dfs(Node *v, double minRes = DBL_MAX){
        if(v == t || !dcmp(minRes)) return minRes;
        double sum = 0;
        for(Edge *&e = v->cur; e; e = e->next){
            if(e->to->d == v->d + 1){
                double flow = dfs(e->to, std::min(minRes, e->res));
                if(dcmp(flow) > 0){
                    sum += flow, minRes -= flow;
                    e->res -= flow, e->rev->res += flow;
 
                    if(!dcmp(minRes)) break;
                }
            }
        }
        return sum;
    }
 
    inline double maxFlow(int s, int t, int n){
        Dinic::s = node(s), Dinic::t = node(t), Dinic::n = n;
 
        for(Node *v = node(0); v != node(n); v++) for(Edge *e = v->e; e; e = e->next) e->res = e->cap;
 
        double ans = 0;
        while(bfs()) ans += dfs(Dinic::s);
        return ans;
    }
}
 
int n, m;
int a[MAX_N + 1], b[MAX_M + 1];
int s, t;
 
double sum;
 
inline int robot(int i){
    return i;
}
 
inline int gun(int i){
    return i + n;
}
 
inline bool check(double x){
    for(int i = 1; i <= m; i++){
        Edge *e = node(gun(i))->e->rev;
        e->cap = x * b[i];
    }
 
    return equal(Dinic::maxFlow(s, t, n + m + 2), sum);
}
 
inline double solve(){
    sum = std::accumulate(a + 1, a + n + 1, 0);
    double min = *std::min_element(b + 1, b + m + 1);
 
    double l = 0, r = sum / min;
    for(int i = 0; i <= 30; i++){
        double mid = (l + r) / 2;
        if(check(mid)) r = mid; else l = mid;
    }
 
    return (l + r) / 2;
}
 
int main(){
    scanf("%d%d", &n, &m);
 
    s = 0, t = n + m + 1;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= m; i++) scanf("%d", &b[i]);
 
    for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++){
        int x;
        scanf("%d", &x);
        if(x) addEdge(gun(i), robot(j), DBL_MAX);
    }
 
    for(int i = 1; i <= n; i++) addEdge(robot(i), t, a[i]);
    for(int i = 1; i <= m; i++) addEdge(s, gun(i), 0);
 
    printf("%.6f\n", solve());
 
    return 0;
}

就是这样啦～