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

Problem

【SDOI2015】星际战争

Description

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

Input

第一行，两个整数，、。
第二行，个整数，、。
第三行，个整数，、。
接下来的行，每行个整数，这些整数均为或者。这部分中的第行的第个整数为表示第个激光武器不可以攻击第个巨型机器人，为表示第个激光武器可以攻击第个巨型机器人。

Output

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

Sample Input

Sample Output

1.300000

HINT

样例说明
战斗开始后的前秒，激光武器攻击号巨型机器人，激光武器攻击号巨型机器人。号巨型机器人被完全摧毁，号巨型机器人还剩余的装甲值；
接下来的秒，激光武器、同时攻击号巨型机器人。号巨型机器人被完全摧毁。
数据范围
对于全部的数据，，，，输入数据保证军团一定能摧毁军团的所有巨型机器人

标签：二分答案 网络流

Solution

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

Code

#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;
}