【CodeForces】【网络流】【带权二分】739E-Gosha is hunting

CodeForces 739E Gosha is hunting

题目大意

有$N$个精灵，Gosha 手中有$A$个普通球和$B$个超级球，已知第$i$个精灵被普通球捕获的概率为$p_i$，被超级球捕获的概率为$u_i$。Gosha 可以先决定对哪些精灵扔普通球，哪些扔超级球。

Gosha 想知道在最优决策下，捕获的精灵的最大期望数量。

注意可以向一个精灵扔最多一个普通球和超级球。这时这个精灵被这些球中的任何一个球捕获到都算作被捕获，但其他的球仍然被消耗掉。

分析

考虑对一个精灵的四种扔球情况的期望：

1. 不扔球：捕获概率和期望都是$0$；
2. 扔一个普通球：捕获概率为$p_i$，对答案贡献$1\times p_i=p_i$；
3. 扔一个超级球：捕获概率为$u_i$，对答案贡献为$1\times u_i=u_i$；
4. 扔一个超级球和一个普通球：捕获概率为$1?(1?p_i)(1?u_i)=p_i+u_i?p_i{u}_i$，对答案贡献为$p_i+u_i?p_i{u}_i$。

我们很自然地想到两种做法：

网络流

我们用边的容量去限制球的使用个数，用费用去计算贡献。

球的总个数限制可以用边的容量去限制：建立两个节点$P,U$，分别向源点连一条容量为$A,B$，费用为$0$的边。

那么对于第$i$个精灵，我们从$P$连一条到第$i$个点，容量为$1$，费用为$p_i$的边，从$U$连一条到第$i$个点，容量为$1$，费用为$u_i$的边。

那么精灵怎么向汇点连边？

考虑到若过来的流量只有$1$，对于情况2,3，显然贡献为$p_i$或者$u_i$，这是没问题的。

但过来的流量是$2$呢？我们需要减掉$p_i\times u_i$。

换句话说我们需要更大的流量才能够获得$?p_i{u}_i$的贡献。

一种有效的方法是将一条边拆成两条：一条费用为$0$，容量为$1$的边和一条费用为$?p_i{u}_i$，容量为$1$的边。

由于费用流是按照最短路来增广的，所以一定会先去那条费用为$0$的边，再去费用为$1$的边。故这样建图没有问题。

注意我们要求的是最大费用最大流，所以为了将这个问题变成最小费用最大流，代码中所有的边权都取反了。

带权二分

考虑用 DP 来解决这道题：

定义状态$f(i,j,k)$为对前$i$个精灵用了$j$个普通球和$k$个精灵球的最大期望。

转移就按照上面讲的四种情况来就是了。最终答案就是$f(N,A,B)$了。

换句话说我们最大的答案一定是将$A,B$用完了的。

似乎有点像带权二分。

由于我们需要最大化答案，所以我们一定是先扔期望大的再扔期望小的，所以最优解的增长趋势一定会越来越慢，所以这个函数就是个凸的。 （手动脑补三维空间上的函数图像。。。）

于是我们就可以愉快地带权二分套带权二分了QAQ。。。

参考代码

备注： 这题卡精度，不用 EPS 和 EPS 太小都过不去 QAQ。。。

经测试$10^{?7}$当做 EPS 是一个不错的选择。

写二分时不想卡精度就直接用循环次数好了。。。

网络流

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int Maxn = 2000;
const int Maxm = 1e4;
const int INF = 0x3f3f3f3f;
const double INFDB = (1 << 30);
const double EPS = 1e-7;inline bool cmp(double lhs, double rhs) {
    return lhs - rhs < -EPS;
}
inline bool equal(double lhs, double rhs) {
    return -EPS < lhs - rhs && lhs - rhs < EPS;
}struct MaxCostMaxFlow {
    struct Edge {
    int to, cap;double cos;Edge *nxt, *bak;};Edge pool[Maxm * 2 + 5];Edge *ecnt, *G[Maxn + 5];inline void addedge(int u, int v, int cap, double c) {
    Edge *p = ++ecnt;p->to = v, p->cap = cap, p->cos = c;p->nxt = G[u], G[u] = p;p->bak = p + 1;p = ++ecnt;p->to = u, p->cap = 0, p->cos = -c;p->nxt = G[v], G[v] = p;p->bak = p - 1;}int node, s, t;double d[Maxn + 5];Edge *cpy[Maxn + 5];double cost;void init(int n) {
    ecnt = &pool[0];node = n;for(int i = 1; i <= n; i++)G[i] = NULL;}bool vis[Maxn + 5];int dfs(int u, int tot) {
    if(u == t) return tot;vis[u] = true;int sum = 0;for(;cpy[u] != NULL; cpy[u] = cpy[u]->nxt) {
    int v = cpy[u]->to;double w = cpy[u]->cos;if(!vis[v] && equal(d[v], d[u] + w) && cpy[u]->cap > 0) {
    int delta = dfs(v, min(tot - sum, cpy[u]->cap));cpy[u]->cap -= delta, cpy[u]->bak->cap += delta;cost += cpy[u]->cos * delta;sum += delta;if(sum == tot) break;}}vis[u] = false;return sum;}bool spfa(int _s, int _t) {
    static bool inq[Maxn + 5];memset(inq, false, sizeof inq);for(int i = 1 ; i <= node; i++)d[i] = INFDB, cpy[i] = G[i];queue<int> q;q.push(_s), d[_s] = 0, inq[_s] = true;while(!q.empty()) {
    int u = q.front();q.pop(), inq[u] = false;for(Edge *p = G[u]; p != NULL; p = p->nxt) {
    int v = p->to;if(p->cap > 0 && cmp(d[u] + p->cos, d[v])) {
    d[v] = d[u] + p->cos;if(!inq[v]) {
    inq[v] = true;q.push(v);}}}}return d[_t] != INFDB;}double mcmf(int _s, int _t) {
    s = _s, t = _t, cost = 0;while(spfa(s, t)) {
    memset(vis, false, sizeof vis);dfs(s, INF);}return cost;}
};int N, A, B;
double P[Maxn + 5], U[Maxn + 5];
MaxCostMaxFlow f;int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifscanf("%d %d %d", &N, &A, &B);for(int i = 1; i <= N; i++)scanf("%lf", &P[i]);for(int i = 1; i <= N; i++)scanf("%lf", &U[i]);int s = N + 1, t = N + 2, p = N + 3, u = N + 4;f.init(N + 4);f.addedge(s, p, A, 0), f.addedge(s, u, B, 0);for(int i = 1; i <= N; i++) {
    f.addedge(p, i, 1, -P[i]), f.addedge(u, i, 1, -U[i]);f.addedge(i, t, 1, 0), f.addedge(i, t, 1, P[i] * U[i]);}printf("%lf\n", -f.mcmf(s, t));return 0;
}

带权二分

#include <cstdio>
#include <algorithm>
using namespace std;const int Maxn = 2000;int N, A, B;
double P[Maxn + 5], U[Maxn + 5];double f[Maxn + 5];
int cntp[Maxn + 5], cntu[Maxn + 5];
bool check(double p, double u, int typ) {
    for(int i = 1; i <= N; i++) {
    f[i] = f[i - 1], cntp[i] = cntp[i - 1], cntu[i] = cntu[i - 1];if(f[i - 1] + P[i] - p > f[i])f[i] = f[i - 1] + P[i] - p, cntp[i] = cntp[i - 1] + 1,cntu[i] = cntu[i - 1];if(f[i - 1] + U[i] - u > f[i])f[i] = f[i - 1] + U[i] - u, cntu[i] = cntu[i - 1] + 1,cntp[i] = cntp[i - 1];if(f[i - 1] + U[i] + P[i] - U[i] * P[i] - p - u > f[i])f[i] = f[i - 1] + U[i] + P[i] - U[i] * P[i] - p - u,cntu[i] = cntu[i - 1] + 1, cntp[i] = cntp[i - 1] + 1;}return typ == 0 ? cntu[N] > B : cntp[N] > A;
}int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifscanf("%d %d %d", &N, &A, &B);for(int i = 1; i <= N; i++)scanf("%lf", &P[i]);for(int i = 1; i <= N; i++)scanf("%lf", &U[i]);double lb = 0, ub = 1, lb1, ub1;for(int i = 1; i <= 50; i++) {
    double mid = (lb + ub) / 2;lb1 = 0, ub1 = 1;for(int i = 1; i <= 50; i++) {
    double mid1 = (lb1 + ub1) / 2;if(check(mid, mid1, 0))lb1 = mid1;else ub1 = mid1;}if(check(mid, ub1, 1)) lb = mid;else ub = mid;}check(ub, ub1, 0);printf("%lf\n", f[N] + A * ub + B * ub1);return 0;
}