題意：n個城市，相互可達（有n(n-1)/2條邊），其中有一些道路上面有妖怪，現在，從1號城市出發，隨機挑取一個城市走去，這個道路上的妖怪就會被消滅，求：

在平均情況下，需要走多少步，使得任意兩個城市之間，可以不經過妖怪而相互可達；

(n<=30)

分析：

1、根據題意可知，我們要將每一個可以不經過妖怪的一個個連通分量找出來；

2、然后從一個連通分量走到另一個連通分量，這時肯定進過妖怪；

3、一個一個連通分量，完成了哪幾個連通分量，需要保存，這時，就用集合的方式保存；

4、從一個連通分量，走到另一個連通分量，其概率 n-con/(n-1) ，那么平均要走 n-1 / (n-con)　次；

5、狀態轉移，下一個狀態s|(i<<n)，和走向這個狀態的概率；

#include <bits/stdc++.h>using namespace std;int n,m; vector<int> g[35]; int cnt; int num[35]; bool vis[35];int dfs(int u) {int count = 1;vis[u] = 1;for(int i=0;i<g[u].size();i++) {int v = g[u][i];if(!vis[v])count+=dfs(v);}return count; }map<int,double> f;double dp(int s) {if(f[s]>1e-9)return f[s];int con = 0;for(int i=0;i<cnt;i++)if(s&(1<<i))con+=num[i];if(con==n)return f[s] = 0;f[s] = (n-1)*1.0/(n-con);for(int i=0;i<cnt;i++) {if(!(s&(1<<i)))f[s] +=dp(s|(1<<i))*num[i]*1.0/(n-con);}return f[s]; }int main() {int t;scanf("%d",&t);int kase = 0;while(t--) {scanf("%d%d",&n,&m);f.clear();for(int i=0;i<=n;i++)g[i].clear();cnt = 0;memset(vis,0,sizeof(vis));memset(num,0,sizeof(num));int u,v;for(int i=0;i<m;i++) {scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}for(int i=1;i<=n;i++) {if(!vis[i])num[cnt++] = dfs(i);}printf("Case %d: %lf\n",++kase,dp(1));}return 0; } View Code

?

轉載于:https://www.cnblogs.com/TreeDream/p/7076631.html

總結

以上是生活随笔為你收集整理的Uva 11600 期望DP的全部內容，希望文章能夠幫你解決所遇到的問題。

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