企业网站服务器选择,做网站全体教程,数据库怎么建立wordpress,wordpress 外教 缩略图Acwing 217. 绿豆蛙的归宿
题意#xff1a;
给出一个有向无环的连通图#xff0c;起点为 1#xff0c;终点为 N#xff0c;每条边都有一个长度。
数据保证从起点出发能够到达图中所有的点#xff0c;图中所有的点也都能够到达终点。
绿豆蛙从起点出发#xff0c;走向…Acwing 217. 绿豆蛙的归宿
题意
给出一个有向无环的连通图起点为 1终点为 N每条边都有一个长度。
数据保证从起点出发能够到达图中所有的点图中所有的点也都能够到达终点。
绿豆蛙从起点出发走向终点。
到达每一个顶点时如果有 K 条离开该点的道路绿豆蛙可以选择任意一条道路离开该点并且走向每条路的概率为 1/K。
现在绿豆蛙想知道从起点走到终点所经过的路径总长度的期望是多少
题解
这个文章讲的不错 设dp[x]表示状态为x到终点n的期望路径总长显然dp[n] 0,所以要从dp[n]倒着推dp[1] 我们设一条有向边x-y,那么就有 dp[x] P * ∑dp[y] w[x-y] P (1/degree(x))degree(x)为x的出度有多少出度说明有多少种选择概率就是倒数 w表示转移对答案的贡献 dp可以通过记忆化搜索求也就通过拓扑排序求
代码
记忆化搜索
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn3e59;
vectorpairint,int vec[maxn];
double dp[maxn];
int n,m;
double dfs(int u){if(un)return 0;if(dp[u])return dp[u];for(int i0;ivec[u].size();i){int vvec[u][i].first;int wvec[u][i].second;dp[u]dfs(v)w;}dp[u]dp[u]/int(vec[u].size());return dp[u];
}
int main()
{cinnm;for(int i1;im;i){int u,v,w;cinuvw;vec[u].push_back({v,w});}printf(%.2f,dfs(1));
}
拓扑排序
时间复杂度O(nm)
#includeiostream
#includecstdio
#includecmath
#includealgorithm
#includequeue
#includecstring
using namespace std;
typedef long long ll;
const int inf1e97;
inline int read()//读优
{int p0,f1;char cgetchar();while(c0||c9){if(c-)f-1;cgetchar();}while(c0c9){pp*10c-0;cgetchar();}return f*p;}
const int maxn100003;
const int maxm200003;
struct Edge
{int from,to,w;
}p[maxm];
int n,m,cnt,head[maxm],in[maxn],dg[maxn];
double f[maxn];//f[x]表示x点到终点n的期望路径总长
inline void add_edge(int x,int y,int W)//加边
{cnt;p[cnt].fromhead[x];head[x]cnt;p[cnt].toy;p[cnt].wW;
}
inline void toposort()//拓扑排序
{queue int q;q.push(n);while(!q.empty()){int xq.front();q.pop();for(int ihead[x];i;ip[i].from){int yp[i].to;f[y](f[x]p[i].w)/dg[y];//dp转移 if(!(--in[y]))q.push(y);}}
}
int main()
{nread(),mread();for(int i1;im;i){int xread(),yread(),wread();add_edge(y,x,w);//反向建图 in[x],dg[x];}toposort();printf(%.2lf\n,f[1]);return 0;
}
