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$ 两个点限制球的个数。
- 连 $s$ 到 $A$,流量 $a$,费用 $0$,连 $s$ 到 $B$,流量 $b$,费用 $0$;
- 连 $A$ 到 $i$,流量 $1$,费用 $p _ a$,连 $B$ 到 $i$,流量 $1$,费用 $p_b$;
- 连 $i$ 到 $t$,流量 $1$,费用 $0$;
- 连 $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; }
近期评论