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 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
| #include <cstdio> #include <algorithm> #include <queue> using namespace std; const double eps = 1e-10; const int N = 2e3 + 10, M = 2e4 + 10, inf = 1e5; bool vis[N]; int n, st, ed, A, B, pre[N], incf[N]; double p1[N], p2[N], d[N], f[M]; int idx = -1, hd[N], nxt[M], edg[M], wt[M]; bool spfa() { for (int i = st; i <= ed; i++) d[i] = -inf; d[st] = 0; for (int i = st; i <= ed; i++) incf[i] = 0; incf[st] = inf; queue<int> q; q.push(st); vis[st] = true; while (!q.empty()) { int t = q.front(); q.pop(); vis[t] = false; for (int i = hd[t]; ~i; i = nxt[i]) if (d[t] + f[i] > d[edg[i]] + eps && wt[i]) { d[edg[i]] = d[t] + f[i]; pre[edg[i]] = i; incf[edg[i]] = min(wt[i], incf[t]); if (!vis[edg[i]]) { q.push(edg[i]); vis[edg[i]] = true; } } } return incf[ed] > 0; } double ek() { double res = 0; while (spfa()) { int t = incf[ed]; res += t * d[ed]; for (int i = ed; i != st; i = edg[pre[i] ^ 1]) { wt[pre[i]] -= t; wt[pre[i] ^ 1] += t; } } return res; } void add(int a, int b, int c, double d) { nxt[++idx] = hd[a]; hd[a] = idx; edg[idx] = b; wt[idx] = c; f[idx] = d; } int main() { scanf("%d%d%d", &n, &A, &B); st = 0, ed = n + 3; for (int i = st; i <= ed; i++) hd[i] = -1; add(st, n + 1, A, 0); add(n + 1, st, 0, 0); add(st, n + 2, B, 0); add(n + 2, st, 0, 0); for (int i = 1; i <= n; i++) scanf("%lf", &p1[i]); for (int i = 1; i <= n; i++) scanf("%lf", &p2[i]); for (int i = 1; i <= n; i++) { add(n + 1, i, 1, p1[i]); add(i, n + 1, 0, -p1[i]); add(n + 2, i, 1, p2[i]); add(i, n + 2, 0, -p2[i]); add(i, ed, 1, 0); add(ed, i, 0, 0); add(i, ed, 1, -p1[i] * p2[i]); add(ed, i, 0, p1[i] * p2[i]); } printf("%lf", ek()); return 0; }
|