BZOJ 3036: 绿豆蛙的归宿
正文索引 [隐藏]
Description
随着新版百度空间的下线，Blog宠物绿豆蛙完成了它的使命，去寻找它新的归宿。
给出一个有向无环的连通图，起点为1终点为N，每条边都有一个长度。绿豆蛙从起点出发，走向终点。
到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。
现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？
Input
第一行: 两个整数 N M，代表图中有N个点、M条边
第二行到第 1+M 行: 每行3个整数 a b c，代表从a到b有一条长度为c的有向边
Output
从起点到终点路径总长度的期望值，四舍五入保留两位小数。
Sample Input
4 4
1 2 1
1 3 2
2 3 3
3 4 4
Sample Output
7.00
HINT
对于100%的数据 N<=100000，M<=2*N
题解
反过来递推就可以了！
Orz数组开小了！把我一页的1A给ShutDown了OwQ！果然水题不能掉以轻心！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
//WNJXYK //while(true) RP++; #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cstring> using namespace std; const int Maxn=100010; const int Maxm=2*Maxn; struct Edge{ int v,nxt; double w; Edge(){} Edge(int v0,int n0,double w0){ v=v0; nxt=n0; w=w0; } }; Edge e[Maxm]; int head[Maxn]; double siz[Maxn]; int nume; inline void addEdge(int u,int v,double w){ e[++nume]=Edge(v,head[u],w); head[u]=nume; siz[u]+=1.0; } int n,m; int x,y; int w; double dist[Maxn]; bool vis[Maxn]; void Dfs(int x){ vis[x]=true; for (int i=head[x];i;i=e[i].nxt){ int v=e[i].v; if (!vis[v]) Dfs(v); dist[x]+=e[i].w+dist[v]; } if (siz[x]) dist[x]/=siz[x]; } int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&w); addEdge(x,y,(double)w); } Dfs(1); printf("%.2lf\n",dist[1]); return 0; } |
原文链接：BZOJ 3036: 绿豆蛙的归宿
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!