链接

BZOJ 3993

题解

这道题挺棵的……

二分答案t，然后源点向武器连t * b[i], 武器向能攻击的敌人连1, 敌人向汇点连a[i]，如果最大流等于所有敌人的a[i]之和则可行。

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

typedef long long ll;

#define enter putchar('\n')

#define space putchar(' ')

template <class T>

void read(T &x){

    char c;

    bool op = 0;

    while(c = getchar(), c > '9' || c < '0')

	if(c == '-') op = 1;

    x = c - '0';

    while(c = getchar(), c >= '0' && c <= '9')

	x = x * 10 + c - '0';

    if(op) x = -x;

}

template <class T>

void write(T x){

    if(x < 0) putchar('-'), x = -x;

    if(x >= 10) write(x / 10);

    putchar('0' + x % 10);

}

const int N = 233, M = 1000005, INF = 0x3f3f3f3f;

const double eps = 0.00001;

int n, m, src, des, sum, a[N], b[N];

bool conn[N][N];

int ecnt = 1, adj[N], cur[N], dis[N], go[M], nxt[M];

double cap[M];

void ADD(int u, int v, double _cap){

    go[++ecnt] = v;

    nxt[ecnt] = adj[u];

    adj[u] = ecnt;

    cap[ecnt] = _cap;

}

void add(int u, int v, double _cap){

    ADD(u, v, _cap);

    ADD(v, u, 0);

}

bool bfs(){

    static int que[N], qr;

    for(int i = 1; i <= des; i++)

	cur[i] = adj[i], dis[i] = -1;

    que[qr = 1] = src, dis[src] = 0;

    for(int ql = 1; ql <= qr; ql++){

	int u = que[ql];

	for(int e = adj[u], v; e; e = nxt[e])

	    if(cap[e] > 0 && dis[v = go[e]] == -1){

		dis[v] = dis[u] + 1, que[++qr] = v;

		if(v == des) return 1;

	    }

    }

    return 0;

}

double dfs(int u, double flow){

    if(u == des) return flow;

    double ret = 0, delta;

    for(int &e = cur[u], v; e; e = nxt[e])

	if(cap[e] > 0 && dis[v = go[e]] == dis[u] + 1){

	    delta = dfs(v, min(cap[e], flow - ret));

	    if(delta > 0){

		cap[e] -= delta;

		cap[e ^ 1] += delta;

		ret += delta;

		if(abs(flow - ret) < eps) return ret;

	    }

	}

    dis[u] = -1;

    return ret;

}

double maxflow(){

    double ret = 0;

    while(bfs()) ret += dfs(src, INF);

    return ret;

}

bool check(double mid){

    ecnt = 1;

    for(int i = 1; i <= des; i++)

	adj[i] = 0;

    for(int i = 1; i <= m; i++)

	add(src, i, mid * b[i]);

    for(int i = 1; i <= m; i++)

	for(int j = 1; j <= n; j++)

	    if(conn[i][j])

		add(i, j + m, INF);

    for(int i = 1; i <= n; i++)

	add(i + m, des, a[i]);

    return abs(maxflow() - sum) < eps;

}

int main(){

    read(n), read(m), src = n + m + 1, des = src + 1;

    for(int i = 1; i <= n; i++) read(a[i]), sum += a[i];

    for(int i = 1; i <= m; i++) read(b[i]);

    for(int i = 1; i <= m; i++)

	for(int j = 1; j <= n; j++)

	    read(conn[i][j]);

    double l = 0, r = 100000, mid;

    while(r - l > 0.0001){

	mid = (l + r) / 2;

	if(check(mid)) r = mid;

	else l = mid;

    }

    printf("%lf\n", l);

    return 0;

}