题目地址：洛谷：【P3324】[SDOI2015]星际战争 – 洛谷、BZOJ：Problem 3993. — [SDOI2015]星际战争

题目描述

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

输入输出格式

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

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

输入输出样例

输入样例#1：

2 2
3 10
4 6
0 1
1 1

输出样例#1：

1.300000

说明

【样例说明1】
战斗开始后的前0.5秒，激光武器1攻击2号巨型机器人，激光武器2攻击1号巨型机器人。1号巨型机器人被完全摧毁，2号巨型机器人还剩余8的装甲值；
接下来的0.8秒，激光武器1、2同时攻击2号巨型机器人。2号巨型机器人被完全摧毁。
对于全部的数据，1<=N, M<=50，1<=Ai<=10510^5105 ，1<=Bi<=1000，输入数据保证X军团一定能摧毁Y军团的所有巨型机器人

题解

这个问题本身很难办，因为一个武器无法同时攻击多个目标，这一点在常规的网络流算法中难以控制。既然如此，我们考虑转换为判定问题，判断所给时间内是否能打败。这个我们可以用最大流跑，建一个源→武器→机器人→汇的图，其中源→武器的容量为武器在这段时间内的攻击输出（即t \cdot B_i），机器人→汇的容量为机器人的装甲值。只要汇点可以满流，就说明可以打败。
至于精度问题，要求1e-3的误差，那么扩大1e4倍即可解决问题。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>

#include <algorithm>
#include <queue>

typedef long long LL;

const int MAXN = 105, MAXM = 500005;
const LL INF = 1e15;
const double EPS = 1e-6;

struct Edge {
    int to; 
    LL cap;
    int nxt;
} gra[MAXM << 1];
int head[MAXN], tot;

inline void addedge(int u, int v, LL cap) {
    gra[tot] = Edge {v, cap, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, head[v]}; head[v] = tot++;
}

inline void init() {
    memset(head, -1, sizeof(head));
    tot = 0;
}

int level[MAXN];
bool vis[MAXN];
std::queue<int> que;

inline bool bfs(int s, int t) {
    memset(level, -1, sizeof(level));
    level[s] = 0; que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(level[v] == -1 && gra[i].cap > 0) {
                level[v] = level[u] + 1;
                que.push(v);
            }
        }
    }
    return level[t] != -1;
}

inline LL dfs(int u, int t, LL left) {
    if(left == 0 || u == t) return left;
    vis[u] = true;
    LL flow = 0;
    for(int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(!vis[v] && gra[i].cap > 0 && level[v] == level[u] + 1) {
            int d = dfs(v, t, std::min(left, gra[i].cap));
            if(d > 0) {
                gra[i].cap -= d; gra[i ^ 1].cap += d;
                flow += d; left -= d;
                if(left == 0) {
                    level[u] = -1;
                    return flow;
                }
            }
        }
    }
    return flow;
}

inline LL dinic(int s, int t) {
    LL flow = 0;
    while(bfs(s, t)) {
        memset(vis, 0, sizeof(vis));
        LL f;
        while(f = dfs(s, t, INF)) {
            flow += f;
        }
    }
    return flow;
}

LL n, m, a[MAXN], b[MAXN], S, T, sum;
bool canatt[MAXN][MAXN];

inline bool check(LL mid) {
    init();
    for(int i = 1; i <= n; i++) {
        addedge(S, i, a[i]);
    }
    for(int i = 1; i <= m; i++) {
        addedge(i + n, T, b[i] * mid);
    }
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            if(canatt[i][j]) addedge(j, i + n, INF);
        }
    }
    LL flow = dinic(S, T);
    return flow >= sum;
}

int main() {
    scanf("%lld%lld", &n, &m);
    S = n + m + 1; T = S + 1;
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        a[i] *= 1e4;
        sum += a[i];
    }
    for(int i = 1; i <= m; i++) {
        scanf("%lld", &b[i]);
    }
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            scanf("%d", &canatt[i][j]);
        }
    }
    LL l = 0, r = 1e9, mid;
    while(r - l > 1) {
        mid = (l + r) >> 1; 
        if(check(mid)) r = mid; else l = mid;
    }
    printf("%.4lf", r / 1e4);
    return 0;
}