CodeForces - 739E Gosha is hunting(最大费用最大流+思维建边)

题目链接：点击查看

题目大意：给出两种精灵球来捉n只精灵，方便起见我们称为a个aa球和b个bb球，对于每只精灵：

若单独用aa球捕捉，成功的概率为p

若单独用bb球捕捉，成功的概率为u

若同时用aa球和bb球捕捉，成功的概率为1-(1-u)*(1-p)

某一种精灵球只能对每一只精灵使用一次，也就是说不能先用aa球后再用bb球，不过可以同时使用aa球和bb球，问最后最大的捕捉成功的期望是多少

题目分析：首先将题目要求的期望转换一下吧，估计看到期望这两个字就已经能把人吓跑了，所谓期望，翻译一下其实就是平均值，因为每只精灵的数量为1，那么捕捉概率*数量就是这个题目的期望了，所以转换一下这个题目要求的期望其实就是对于每一只精灵的捕捉成功率之和

那么假设没有条件3，我们就可以直接建费用流的图了，不用多解释了吧：

源点->两种精灵球，流量为各自的数量，花费为0

每一种精灵球->每个精灵，流量为1，花费为各自捕捉成功的概率

每个精灵->汇点，流量为1，花费为0

这样跑一遍最大费用最大流就是答案了。。。可以上说的是没有条件3的情况下的做法，如果要是加上条件三我们该怎么考虑呢

其实先要对那个概率化简一下，1-(1-u)*(1-p)化简一下就变成了u+p-u*p，可以看到，如果我们将两个精灵球同时都选择了的话，答案会多了一个u*p，所以我们减掉就好了。。因为选择一个球的概率正常还是u或p，那么如果再选择另一个球的话，答案就变成了u+p，但我们一开始建边设置的流量只有1，所以我们会需要将流量扩大一倍，倒不如说我们需要新建一条边来连接每一只精灵和汇点，流量为1，花费就是-u*p了，这样的话我们如果只选择一个精灵球的话，会正常走花费为0的边，而如果要同时选择两个球的话，才会走到当前这个边，最后算出的结果自然也就是u+p-u*p啦

正确建边方法：

源点->两种精灵球，流量为各自的数量，花费为0

每一种精灵球->每个精灵，流量为1，花费为各自捕捉成功的概率

每个精灵->汇点，流量为1，花费为0

每个精灵->汇点，流量为1，花费为-u*p

然后就是对于浮点数跑费用流的话，需要手动改一下模板内置的实现，还有就是记得加上eps，不然会超时

代码：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e3+100;//点const int M=2e4+100;//边const double eps=1e-8;struct Edge {int to,w,next;double cost; }edge[M];int head[N],cnt;void addedge(int u,int v,int w,double cost) {edge[cnt].to=v;edge[cnt].w=w;edge[cnt].cost=cost;edge[cnt].next=head[u];head[u]=cnt++;edge[cnt].to=u;edge[cnt].w=0;edge[cnt].cost=-cost;edge[cnt].next=head[v];head[v]=cnt++; }int incf[N],pre[N];double d[N],p[N],u[N];bool vis[N];bool spfa(int s,int t) {for(int i=0;i<N;i++)d[i]=-1e10;memset(vis,false,sizeof(vis));memset(pre,-1,sizeof(pre));queue<int>q;q.push(s);vis[s]=true;incf[s]=inf;d[s]=0;while(!q.empty()){int u=q.front();q.pop();vis[u]=false;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;int w=edge[i].w;double cost=edge[i].cost;if(!w)continue;if(eps+d[v]<d[u]+cost){d[v]=d[u]+cost;pre[v]=i;incf[v]=min(incf[u],w);if(!vis[v]){vis[v]=true;q.push(v);}}}}return pre[t]!=-1; }double update(int s,int t) {int x=t;while(x!=s){int i=pre[x];edge[i].w-=incf[t];edge[i^1].w+=incf[t];x=edge[i^1].to;}return d[t]*incf[t]; }void init() {memset(head,-1,sizeof(head));cnt=0; }double solve(int st,int ed) {double ans=0;while(spfa(st,ed))ans+=update(st,ed);return ans; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);init();int n,a,b,st=N-1,ed=st-1;scanf("%d%d%d",&n,&a,&b);int aa=N-3,bb=aa-1;addedge(st,aa,a,0);addedge(st,bb,b,0);for(int i=1;i<=n;i++)scanf("%lf",p+i);for(int i=1;i<=n;i++)scanf("%lf",u+i);for(int i=1;i<=n;i++){addedge(aa,i,1,p[i]);addedge(bb,i,1,u[i]);addedge(i,ed,1,0);addedge(i,ed,1,-p[i]*u[i]);}printf("%f\n",solve(st,ed));return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 739E Gosha is hunting(最大费用最大流+思维建边)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。