BZOJ3993 [SDOI2015]星际战争

时间:2021-04-27 21:29:24

二分答案。。。然后最大流验证是否可行。。。

没了,好水啊QAQ

 /**************************************************************
Problem: 3993
User: rausen
Language: C++
Result: Accepted
Time:40 ms
Memory:1156 kb
****************************************************************/ #include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
typedef double lf;
const int N = ;
const lf inf = 1e10;
const lf eps = 1e-;
const int M = N * N << ; inline int read(); struct edge {
int next, to;
lf f;
edge(int _n = , int _t = , lf _f = 0.0) : next(_n), to(_t), f(_f) {}
} e[M]; int n, m, S, T;
int b[N];
int first[N], tot = ;
int q[N], d[N]; inline void Add_Edges(int x, int y, lf z) {
e[++tot] = edge(first[x], y, z), first[x] = tot;
e[++tot] = edge(first[y], x, ), first[y] = tot;
} #define y e[x].to
#define p q[l]
bool bfs() {
static int l, r, x;
memset(d, -, sizeof(d));
d[q[] = S] = ;
for (l = r = ; l != r + ; ++l)
for (x = first[p]; x; x = e[x].next)
if (!~d[y] && e[x].f > eps) {
d[q[++r] = y] = d[p] + ;
if (y == T) return ;
}
return ;
}
#undef p lf dfs(int p, lf lim) {
if (p == T || !lim) return lim;
int x;
lf tmp, rest = lim;
for (x = first[p]; x && rest > eps; x = e[x].next)
if (d[y] == d[p] + && ((tmp = min(e[x].f, rest)) > eps)) {
rest -= (tmp = dfs(y, tmp));
e[x].f -= tmp, e[x ^ ].f += tmp;
if (!rest) return lim;
}
if (rest > eps) d[p] = -;
return lim - rest;
} inline bool check(lf t) {
static int x;
for (x = ; x <= tot; x += )
e[x].f += e[x ^ ].f, e[x ^ ].f = ;
for (x = first[S]; x; x = e[x].next)
e[x].f = b[y - n] * t;
while (bfs()) dfs(S, inf);
for (x = first[T]; x; x = e[x].next)
if (e[x ^ ].f > eps) return ;
return ;
}
#undef y int main() {
int i, j;
lf l, r, mid;
n = read(), m = read();
S = n + m + , T = S + ;
for (i = ; i <= n; ++i)
Add_Edges(i, T, read());
for (i = ; i <= m; ++i)
b[i] = read(), Add_Edges(S, n + i, );
for (i = ; i <= m; ++i)
for (j = ; j <= n; ++j)
if (read() == ) Add_Edges(n + i, j, inf);
l = , r = 5e6;
while (r - l > eps) {
mid = (l + r) / 2.0;
if (check(mid)) r = mid;
else l = mid;
}
printf("%.6lf\n", (l + r) / 2.0);
return ;
} inline int read() {
static int x;
static char ch;
x = , ch = getchar();
while (ch < '' || '' < ch)
ch = getchar();
while ('' <= ch && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x;
}