bzoj 3993 [SDOI2015]星际战争

Description

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

Input

第一行，两个整数，N、M。

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

Output

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

Sample Input

2 2

3 10

4 6

0 1

1 1

Sample Output

1.300000

HINT

【样例说明1】

战斗开始后的前0.5秒，激光武器1攻击2号巨型机器人，激光武器2攻击1号巨型机器人。1号巨型机器人被完全摧毁，2号巨型机器人还剩余8的装甲值；

接下来的0.8秒，激光武器1、2同时攻击2号巨型机器人。2号巨型机器人被完全摧毁。

对于全部的数据，1<=N, M<=50，1<=Ai<=105，1<=Bi<=1000，输入数据保证X军团一定能摧毁Y军团的所有巨型机器人

题解

我看标签是小数网络流还以为是什么高级的东西，其实就是把流量乘到误差以外，最后除一下。

显然具有单调性，二分了网络流check就好了，建图很裸

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define N 10010
using namespace std;
const int inf = 0x3f3f3f3f;
struct flows {
    struct node {
        int to, next;
        long long flow;
    } e[N * 20];
    long long tot, st[N], dis[N], cur[N];
    void init() {
        tot = -1, memset(e, -1, sizeof e),
        memset(st, -1, sizeof st);
    }
    void add(int x, int y, long long z) {
        e[++tot].to = y;
        e[tot].flow = z;
        e[tot].next = st[x];
        st[x] = tot;
    }
    void add_edge(int x, int y, long long z) {
//      printf("add:%d %d %d\n", x, y, z);
        add(x, y, z), add(y, x, 0);
    }
    queue <int> que;
    int bfs(int S, int T) {
        memcpy(cur, st, sizeof st);
        memset(dis, 0, sizeof dis);
        while (!que.empty()) que.pop();
        que.push(S);
        dis[S] = 1;
        while(!que.empty()) {
            int now = que.front();
            que.pop();
            for (int i = st[now]; ~i; i = e[i].next)
                if (e[i].flow && !dis[e[i].to]) {
                    dis[e[i].to] = dis[now] + 1;
                    if (e[i].to == T) return 1;
                    que.push(e[i].to);
                }
        }
        return 0;
    }
    long long finds(int now, int T, long long flow) {
        if (now == T)
            return flow;
        long long f;
        for (int i = cur[now]; ~i; i = e[i].next) {
            cur[now] = i;
            if (e[i].flow && dis[e[i].to] == dis[now] + 1 &&
                (f = finds(e[i].to, T, min(flow, e[i].flow)))) {
                e[i].flow -= f;
                e[i^1].flow += f;
                return f;
            }
        }
        return 0;
    }
    long long dinic(int S, int T) {
        long long flow = 0, x;
        while(bfs(S, T)) {
            while(x = finds(S, T, inf)) {
                flow += x;
            }
        }
        return flow;
    }
}flow;
int n, m, S, T, x, y, z, c;
long long a[110], b[110], all;
int p[100][100];
bool check(long long now) {
    flow.init();
    S = 0, T = n + m + 1;
    for (int i = 1; i <= m; ++i)
        flow.add_edge(S, i, now * b[i]);
    for (int i = 1; i <= n; ++i)
        flow.add_edge(i + m, T, a[i]);
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            if (p[i][j])
                flow.add_edge(i, j + m, inf);
    long long ans = flow.dinic(S, T);
    return ans == all;
}
main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &a[i]), a[i] *= 1000ll, all += 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", &p[i][j]);
    long long l = 0, r = 5000000000ll, ans = 0;
    while (l <= r) {
        long long mid = l + r >> 1;
        if (check(mid))
            r = mid - 1, ans = mid;
        else
            l = mid + 1;
    }
    printf("%.5lf\n", (double)ans / 1000.0);
}