首页 > 代码库 > Uva 11600 期望DP
Uva 11600 期望DP
题意：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;}
Uva 11600 期望DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。