題目鏈接：點(diǎn)擊查看

題目大意：給出兩種精靈球來捉n只精靈，方便起見我們稱為a個(gè)aa球和b個(gè)bb球，對(duì)于每只精靈：

若單獨(dú)用aa球捕捉，成功的概率為p

若單獨(dú)用bb球捕捉，成功的概率為u

若同時(shí)用aa球和bb球捕捉，成功的概率為1-(1-u)*(1-p)

某一種精靈球只能對(duì)每一只精靈使用一次，也就是說不能先用aa球后再用bb球，不過可以同時(shí)使用aa球和bb球，問最后最大的捕捉成功的期望是多少

題目分析：首先將題目要求的期望轉(zhuǎn)換一下吧，估計(jì)看到期望這兩個(gè)字就已經(jīng)能把人嚇跑了，所謂期望，翻譯一下其實(shí)就是平均值，因?yàn)槊恐痪`的數(shù)量為1，那么捕捉概率*數(shù)量就是這個(gè)題目的期望了，所以轉(zhuǎn)換一下這個(gè)題目要求的期望其實(shí)就是對(duì)于每一只精靈的捕捉成功率之和

那么假設(shè)沒有條件3，我們就可以直接建費(fèi)用流的圖了，不用多解釋了吧：

源點(diǎn)->兩種精靈球，流量為各自的數(shù)量，花費(fèi)為0

每一種精靈球->每個(gè)精靈，流量為1，花費(fèi)為各自捕捉成功的概率

每個(gè)精靈->匯點(diǎn)，流量為1，花費(fèi)為0

這樣跑一遍最大費(fèi)用最大流就是答案了。。。可以上說的是沒有條件3的情況下的做法，如果要是加上條件三我們?cè)撛趺纯紤]呢

其實(shí)先要對(duì)那個(gè)概率化簡(jiǎn)一下，1-(1-u)*(1-p)化簡(jiǎn)一下就變成了u+p-u*p，可以看到，如果我們將兩個(gè)精靈球同時(shí)都選擇了的話，答案會(huì)多了一個(gè)u*p，所以我們減掉就好了。。因?yàn)檫x擇一個(gè)球的概率正常還是u或p，那么如果再選擇另一個(gè)球的話，答案就變成了u+p，但我們一開始建邊設(shè)置的流量只有1，所以我們會(huì)需要將流量擴(kuò)大一倍，倒不如說我們需要新建一條邊來連接每一只精靈和匯點(diǎn)，流量為1，花費(fèi)就是-u*p了，這樣的話我們?nèi)绻贿x擇一個(gè)精靈球的話，會(huì)正常走花費(fèi)為0的邊，而如果要同時(shí)選擇兩個(gè)球的話，才會(huì)走到當(dāng)前這個(gè)邊，最后算出的結(jié)果自然也就是u+p-u*p啦

正確建邊方法：

源點(diǎn)->兩種精靈球，流量為各自的數(shù)量，花費(fèi)為0

每一種精靈球->每個(gè)精靈，流量為1，花費(fèi)為各自捕捉成功的概率

每個(gè)精靈->匯點(diǎn)，流量為1，花費(fèi)為0

每個(gè)精靈->匯點(diǎn)，流量為1，花費(fèi)為-u*p

然后就是對(duì)于浮點(diǎn)數(shù)跑費(fèi)用流的話，需要手動(dòng)改一下模板內(nèi)置的實(shí)現(xiàn)，還有就是記得加上eps，不然會(huì)超時(shí)

代碼：

#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;//點(diǎn)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; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 739E Gosha is hunting(最大费用最大流+思维建边)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。