CF739E Gosha is hunting(期望转费用流)

其实这个正解是wqs二分套wqs二分

然而我太菜了不会那么难的,用个费用流水一水

$匹配问题,容易想到网络流$

$把两种球拆分为两个虚点,s分别向其连流量a,b费用0的边$

$这两个虚点向所有精灵连流量1费用为捕捉概率的边$

$但是当两个精灵球流向一个点会出错,不是简单相加p_i+q_i$

而是$p_i+q_i?p_i{q}_i$

这个好办,$i$向$t$连一条流量$1$,费用$0$的边

$i$再向$t$连一条流量$1$,费用$p_i{q}_i$的边

这样流只有$1$的时候肯定优先走第一条边

最大费用最大流(最小费用流边权取反)

#include <bits/stdc++.h>
using namespace std;
const double eps=1e-8;
const int maxn=2e5+10;
const int inf=1e9;
int n,m,s,t,a,b;
double maxflow,mincost;
double dis[maxn];
int head[maxn<<1],cnt=1,incf[maxn],pre[maxn],vis[maxn];
struct edge{int to,nxt,flow; double w;//分别代表 
}d[maxn<<1];
void add(int u,int v,int flow,double w)//最大流量,单位费用
{d[++cnt]=(edge){v,head[u],flow,w},head[u]=cnt;d[++cnt]=(edge){u,head[v],0,-w},head[v]=cnt;
} 
bool spfa()
{queue<int>q;for(int i=0;i<=t;i++)	dis[i]=inf,vis[i]=0;q.push(s);dis[s]=0,vis[s]=1;incf[s] = inf;//初始流量无限大while( !q.empty() ){int u=q.front(); q.pop();vis[u]=0;//出队for(int i=head[u];i;i=d[i].nxt){if( !d[i].flow )	continue;//无流量了	int v=d[i].to;if( dis[v]>dis[u]+d[i].w+eps ){dis[v]=dis[u]+d[i].w;incf[v] = min(incf[u],d[i].flow);//更新当前流量pre[v]=i;//记录从哪条边过来的if( !vis[v] )	vis[v]=1,q.push(v); }}	} if( dis[t]==inf )	return 0;return 1;
}
void dinic()
{while( spfa() ){int x=t;//倒回去找路径maxflow+=incf[t];mincost+=dis[t]*incf[t];int i;while(x != s){i=pre[x];d[i].flow-=incf[t];//减去流量d[i^1].flow+=incf[t];//加上流量x = d[i^1].to;//因为是倒回去,所以利用反向边倒回去 } }
}
double p[maxn],u[maxn];
int main()
{cin >> n >> a >> b;s=0,t=n+3;add(s,n+1,a,0);add(s,n+2,b,0);for(int i=1;i<=n;i++){scanf("%lf",&p[i] );add(n+1,i,1,-p[i]);}for(int i=1;i<=n;i++){scanf("%lf",&u[i] );add(n+2,i,1,-u[i]);add(i,t,1,0);add(i,t,1,u[i]*p[i]);}dinic();printf("%.6lf",-mincost);
}