【CF#739E】Gosha is hunting

  • 本文为博主原创,未经许可不得转载

题目大意:

现在有$n$个神奇宝贝,而你有$a$个普通球和$b$个高级球

每个神奇宝贝可以用一个普通球或一个高级球或两个球同时使用,成功概率为$p[i]$,$u[i]$,$p[i]+u[i]−p[i]\times u[i]$

不能对一个神奇宝贝多次尝试捕捉,求期望最大捕捉数


解析:

费用流建图即可

费用流复杂度好像是n^3

事实上n^3的dp过了……

注意:建图时要把边权乘上一个大常数,以避免小数带来的误差

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
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 100100
#define INF 1e9
using namespace std;
const int chty=1000000;//常数
struct node{int y,next,v,w;}e[MAXN<<1];
int n,A,B,S,T,IdA,IdB,IdC,cnt,ans,len(1),Id[MAXN],Link[MAXN],dis[MAXN],flow[MAXN],vis[MAXN],LE[MAXN],LN[MAXN];
double P[MAXN],u[MAXN];
queue<int>q;
inline int read(){
int x=0,f=1; char ch=getchar();
while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
void insert(int x,int y,int v,int w){
e[++len].next=Link[x];Link[x]=len;e[len].y=y;e[len].v=v;e[len].w=w;
e[++len].next=Link[y];Link[y]=len;e[len].y=x;e[len].v=0;e[len].w=-w;
}
bool spfa(){
for(int i=1;i<=cnt;++i) vis[i]=0;
for(int i=1;i<=cnt;++i) dis[i]=INF;
q.push(S); vis[S]=1; dis[S]=0; flow[S]=INF;
while(!q.empty()){
int x=q.front(); q.pop(); vis[x]=0;
for(int i=Link[x];i;i=e[i].next)if(dis[x]+e[i].w<dis[e[i].y]&&e[i].v){
dis[e[i].y]=dis[x]+e[i].w;
flow[e[i].y]=min(flow[x],e[i].v);
LN[e[i].y]=x; LE[e[i].y]=i;
if(!vis[e[i].y]) vis[e[i].y]=1,q.push(e[i].y);
}
}
if(dis[T]==INF) return 0;
ans-=flow[T]*dis[T];
for(int i=T;i!=S;i=LN[i]) e[LE[i]].v-=flow[T],e[LE[i]^1].v+=flow[T];
return 1;
}
int main(){
//freopen(FILE".in","r",stdin);
//freopen(FILE".out","w",stdout);
n=read(); A=read(); B=read();
S=++cnt; T=++cnt; IdA=++cnt; IdB=++cnt; IdC=++cnt;
for(int i=1;i<=n;++i) Id[i]=++cnt;
for(int i=1;i<=n;++i) scanf("%lf",&P[i]);
for(int i=1;i<=n;++i) scanf("%lf",&u[i]);
insert(S,IdA,A,0); insert(S,IdB,B,0);
for(int i=1;i<=n;++i){
insert(IdA,Id[i],1,-P[i]*chty);
insert(IdB,Id[i],1,-u[i]*chty);
insert(Id[i],IdC,1,0);
insert(Id[i],IdC,1,P[i]*u[i]*chty);
}
insert(IdC,T,INF,0);
while(spfa());
printf("%.18lf\n",(double)ans/chty);
return 0;
}
文章目录
,