BZOJ3993【SDOI2015】星际战争 <二分+网络流>

Posted on Symbols count in article: 1.3k Reading time ≈ 5 mins.

Problem

【SDOI2015】星际战争

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}
Special  Judge\mathrm{Special\;Judge}

Description

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

Input

第一行，两个整数，NN、MM。
第二行，NN个整数，A1A_1、A2A_2 ⋯\cdots ANA_N。
第三行，MM个整数，B1B_1、B2B_2 ⋯\cdots BMB_M。
接下来的MM行，每行NN个整数，这些整数均为00或者11。这部分中的第ii行的第jj个整数为00表示第ii个激光武器不可以攻击第jj个巨型机器人，为11表示第ii个激光武器可以攻击第jj个巨型机器人。

Output

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

Sample Input

1
2
3
4
5
2 2
3 10
4 6
0 1
1 1

Sample Output

1
1.300000

HINT

样例说明
战斗开始后的前0.50.5秒，激光武器11攻击22号巨型机器人，激光武器22攻击11号巨型机器人。11号巨型机器人被完全摧毁，22号巨型机器人还剩余88的装甲值；
接下来的0.80.8秒，激光武器11、22同时攻击22号巨型机器人。22号巨型机器人被完全摧毁。
数据范围
对于全部的数据，1≤N,M≤501\le N,M\le 50，1≤Ai≤1051\le A_i\le 10^5，1≤Bi≤1031\le B_i\le 10^3，输入数据保证XX军团一定能摧毁YY军团的所有巨型机器人

标签：二分答案 网络流

Solution

如果直接处理这个问题，会发现限制有点多，不太好处理。
考虑二分答案。二分最少时间，那么每个激光炮在此时间内可造成的伤害就可以算出，这时只需判断合理分配这些伤害能否使敌方团灭。
发现可以建图跑最大流判断。从源点SS向所有激光炮连边，容量为此激光炮可造成的总伤害。从所有机器人向汇点TT连边，容量为机器人血量。从每个激光炮向其所可以造成伤害的所有机器人连边，容量为∞\infty，这样跑一遍最大流，判断是否等于所有机器人的总血量即可。
建图可以不用全部新建，只用在开始的时候建一个图，二分判断时将所有SS到激光炮的边容量改成Bi×tansB_i\times tans即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
#define MAX_N 100
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define mid (l+r)/2
using namespace std;
typedef double dnt;
struct node {int v, nxt; dnt c;} E[MAX_N*MAX_N*5+500];    dnt sum;
int n, m, s, t, a[MAX_N+5], b[MAX_N+5], mrk[MAX_N+5][MAX_N+5], pre[MAX_N+5], d[MAX_N+5], cnt;
void init() {memset(pre, -1, sizeof(pre)), cnt = 0, s = 0, t = n+m+1;}
void insert(int u, int v, dnt c) {E[cnt].v = v, E[cnt].c = c, E[cnt].nxt = pre[u], pre[u] = cnt++;}
void build() {
    init();
    for (int i = 1; i <= n; i++)	insert(i, t, a[i]), insert(t, i, 0), sum += a[i];
    for (int i = 1; i <= m; i++)	insert(s, i+n, INF), insert(i+n, s, 0);
    for (int i = 1; i <= m; i++)	for (int j = 1; j <= n; j++)	if (mrk[i][j])	insert(i+n, j, INF), insert(j, i+n, 0);
}
bool BFS() {
    queue <int> que;	memset(d, -1, sizeof(d));	que.push(s), d[s] = 0;
    while (!que.empty()) {
        int u = que.front();	que.pop();
        for (int i = pre[u]; ~i; i = E[i].nxt) {
            int v = E[i].v;	if (E[i].c <= EPS || ~d[v])	continue;
            d[v] = d[u]+1;	que.push(v);
        }
    }
    return ~d[t];
}
dnt DFS(int u, dnt flow) {
    if (u == t)	return flow;	dnt ret = 0;
    for (int i = pre[u]; ~i; i = E[i].nxt) {
        int v = E[i].v;	if (E[i].c <= EPS || d[v] != d[u]+1)	continue;
        dnt tmp = DFS(v, min(flow, E[i].c));
        E[i].c -= tmp, E[i^1].c += tmp, ret += tmp, flow -= tmp;
        if (!flow)	break;
    }
    if (!ret)	d[u] = -1;	return ret;
}
bool chk(dnt tans) {
    for (int i = 0; i < cnt; i += 2)	E[i].c += E[i^1].c, E[i^1].c = 0;
    for (int i = pre[s]; ~i; i = E[i].nxt)	E[i].c = (dnt)b[E[i].v-n]*tans;
    dnt tot = 0;	while (BFS())	tot += DFS(s, INF);	return fabs(tot-sum) <= EPS;
}
dnt bi_search(dnt l, dnt r) {
    dnt ret = -1;
    for (int i = 0; i < 100; i++)
        if (chk(mid))	ret = r = mid;
        else	l = mid;
    return ret;
}
int main() {
    scanf("%d%d", &n, &m);
    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++)	scanf("%d", &mrk[i][j]);
    build(), printf("%.5lf", bi_search(0, INF));
    return 0;
}