「题解」「CF739E」Gosha is hunting

CF739E ,一道神奇的 优化动态规划 题目,或者简单的 费用流。

题目链接:CodeForces 739E

题目

题目描述

你要抓神奇宝贝! 现在一共有 $N$ 只神奇宝贝。你有 $a$ 个『宝贝球』和 $b$ 个『超级球』。『宝贝球』抓到第 $i$ 只神奇宝贝的概率是 $p _ i$,『超级球』抓到的概率则是 $u _ i$。不能往同一只神奇宝贝上使用超过一个同种的『球』,但是可以往同一只上既使用『宝贝球』又使用『超级球』(都抓到算一个)。请合理分配每个球抓谁,使得你抓到神奇宝贝的总个数期望最大,并输出这个值。

数据范围

变量数据范围
$n$$2\leq n\leq 2\times 10^3$
$a,b$$0\leq a,b\leq n$

时空限制

题目编号时间限制空间限制
Problem – 739E – Codeforces$5\text{s}$$256\text{MiB}$

题解

CF739E ,一道神奇的 优化动态规划 题目,或者简单的 费用流。

思路

先考虑一下每个神奇宝贝球的贡献:

  • 不用,贡献为 $0$;
  • 只用一个 A 球,贡献为 $p _ a$;
  • 只用一个 B 球,贡献为 $p _ b$;
  • 都用,贡献为 $1-(1-p _ a)(1-p _ b)$;

然后考虑怎么连边。

新建 $A,B$ 两个点限制球的个数。

  1. 连 $s$ 到 $A$,流量 $a$,费用 $0$,连 $s$ 到 $B$,流量 $b$,费用 $0$;
  2. 连 $A$ 到 $i$,流量 $1$,费用 $p _ a$,连 $B$ 到 $i$,流量 $1$,费用 $p_b$;
  3. 连 $i$ 到 $t$,流量 $1$,费用 $0$;
  4. 连 $i$ 到 $t$,流量 $1$,费用 $-p _ ap _ b$。

做最大费用最大流即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define INF 0X3F3F3F3F
#define eps 1e-10

const int MAXN=2000+100;

int n,a,b;
double P[MAXN],Q[MAXN];
int cnt=1,head[MAXN],to[(MAXN*5)<<1],w[(MAXN*5)<<1],Next[(MAXN*5)<<1];
double p[(MAXN*5)<<1];

inline void Add_Edge(reg int u,reg int v,reg int len,reg double val){
    Next[++cnt]=head[u];
    to[cnt]=v;
    w[cnt]=len;
    p[cnt]=val;
    head[u]=cnt;
    return;
}

inline void Add_Tube(reg int u,reg int v,reg int len,reg double val){
    Add_Edge(u,v,len,val);
    Add_Edge(v,u,0,-val);
    return;
}

bool inque[MAXN];
double dis[MAXN];

inline bool SPFA(int s,reg int t){
    queue<int> Q;
    memset(inque,false,sizeof(inque));
    fill(dis+s,dis+t+1,-1e20);
    while(!Q.empty())Q.pop();
    inque[s]=true,dis[s]=0,Q.push(s);
    while(!Q.empty()){
        reg int ID=Q.front();
        Q.pop();
        inque[ID]=false;
        for(reg int i=head[ID];i;i=Next[i])
            if(w[i]&&dis[to[i]]+eps<dis[ID]+p[i]){
                dis[to[i]]=dis[ID]+p[i];
                if(!inque[to[i]]){
                    inque[to[i]]=true;
                    Q.push(to[i]);
                }
            }
    }
    return dis[t]>eps;
}

double Cost;
bool vis[MAXN];
int cur[MAXN];

inline int DFS(reg int ID,reg int t,reg int lim){
    if(ID==t){
        Cost+=lim*dis[t];
        return lim;
    }
    vis[ID]=true;
    reg int flow=0;
    for(reg int &i=cur[ID];i;i=Next[i])
        if(w[i]&&fabs(dis[to[i]]-(dis[ID]+p[i]))<eps&&!vis[to[i]]){
            reg int f=DFS(to[i],t,min(lim-flow,w[i]));
            if(f){
                flow+=f;
                w[i]-=f;
                w[i^1]+=f;
                if(flow==lim)
                    break;
            }
        }
    vis[ID]=false;
    return flow;
}

inline int Dinic(reg int s,reg int t){
    reg int res=0;
    while(SPFA(s,t)){
        memcpy(cur,head,sizeof(head));
        res+=DFS(s,t,INF);
    }
    return res;
}

int main(void){
    scanf("%d%d%d",&n,&a,&b);
    for(reg int i=1;i<=n;++i)
        scanf("%lf",&P[i]);
    for(reg int i=1;i<=n;++i)
        scanf("%lf",&Q[i]);
    reg int s=0,A=n+1,B=n+2,t=n+3;
    Add_Tube(s,A,a,0);
    Add_Tube(s,B,b,0);
    for(reg int i=1;i<=n;++i){
        Add_Tube(A,i,1,P[i]);
        Add_Tube(B,i,1,Q[i]);
        Add_Tube(i,t,1,0);
        Add_Tube(i,t,1,-P[i]*Q[i]);
    }
    Dinic(s,t);
    printf("%.10lf\n",Cost);
    return 0;
}

相关题目