题意:现在有n个精灵,两种精灵球各m1和m2个,每个精灵单独使用第一种精灵球有pi的概率被捕获,单独使用第二种精灵球有ui的概率被捕获,同时使用有1-(1-pi)*(1-ui)的概率被捕获.一种精灵球在一个精灵身上只能用一次,但你可以在一个精灵上用两种精灵球.求最优策略下期望获得精灵的只数.
如果一只精灵上不能同时用两种精灵球,那么就是一个显然的费用流建图,点A表示第一种精灵球,点B表示第二种精灵球,源点向A,B各连一条流量等于对应精灵球数目的边(费用为0),A,B分别向每个精灵连一条流量为1,费用为对应的pi/ui的边,每个精灵连出一条流量为1的边指向汇点,限制只能用一个精灵球,跑最大费用流即可(这里最大费用流等于最大费用最大流,因为精灵球用得越多期望抓捕的精灵数至少不会减少).
现在我们需要考虑同时使用两种精灵球的情况,但并不能简单地把精灵连向汇点的边流量+1,因为这样相加的时候我们重复计算了两种精灵球都生效的情况,这个概率是pi*ui.
那么我们想法减去多出的一部分即可,同时还要保证只使用一个精灵球的时候不减去这部分,那么我们从每个精灵向汇点引出两条流量为1的边,一条费用为0,一条费用为-pi*ui,使用第一个精灵球时最长路一定走费用为0的边,使用第二个精灵球时必须走第二条边从而去除了重复的情况.跑最大费用流即可.
坑点:这道题的费用是实数,spfa比较大小的时候一定要用eps,不然会卡出TLE….
#include<cstdio>
#include<cstring>
const int maxn=,maxm=;
struct edge{
int to,next,w;double cost;
}lst[maxm];int len=,first[maxn];
void addedge(int a,int b,int w,double cost){
lst[len].to=b;lst[len].next=first[a];lst[len].w=w;lst[len].cost=cost;first[a]=len++;
lst[len].to=a;lst[len].next=first[b];lst[len].w=;lst[len].cost=-cost;first[b]=len++;
}
bool inq[maxn];
int s,t,T,head,tail,q[maxn],vis[maxn],prt[maxn];double dis[maxn];
bool spfa(){
head=tail=;q[tail++]=s;inq[s]=true;
vis[s]=++T;dis[s]=;prt[s]=-;
while(head!=tail){
int x=q[head++];head%=maxn;inq[x]=false;
for(int pt=first[x];pt!=-;pt=lst[pt].next){
if(lst[pt].w==)continue;
if(vis[lst[pt].to]!=T||dis[x]+lst[pt].cost-dis[lst[pt].to]>1e-){//这个地方神坑…直接比较大小TLE到死…
vis[lst[pt].to]=T;dis[lst[pt].to]=dis[x]+lst[pt].cost;
prt[lst[pt].to]=pt;
if(!inq[lst[pt].to]){
inq[lst[pt].to]=true;q[tail++]=lst[pt].to;tail%=maxn;
}
}
}
}
return vis[t]==T;
}
double maxcost(){
double ans=;
while(spfa()&&dis[t]>){
ans+=dis[t];
for(int pt=prt[t];pt!=-;pt=prt[lst[pt^].to]){
lst[pt].w--;lst[pt^].w++;
}
}
return ans;
}
double p[maxn],u[maxn];
int main(){
memset(first,-,sizeof(first));
int n,m1,m2;scanf("%d%d%d",&n,&m1,&m2);
s=;t=n+;
addedge(s,n+,m1,);addedge(s,n+,m2,);
for(int i=;i<=n;++i)scanf("%lf",p+i);
for(int i=;i<=n;++i)scanf("%lf",u+i);
for(int i=;i<=n;++i){
addedge(n+,i,,p[i]);addedge(n+,i,,u[i]);
addedge(i,t,,);addedge(i,t,,-p[i]*u[i]);
}
printf("%.5f\n",maxcost());
return ;
}