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;
}
近期评论