題目鏈接：點擊查看

題目大意：給出兩種精靈球來捉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(最大费用最大流+思维建边)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。