路徑長(zhǎng)度

金牌導(dǎo)航 期望-1

題目大意

給出一個(gè)圖，問(wèn)你從1走到n的期望路徑長(zhǎng)度

輸入樣例

4 4 1 2 1 1 3 2 2 3 3 3 4 4

輸出樣例

7.00

數(shù)據(jù)范圍

$1?n?10^5$
$1?m?2\times n$
$1?u,v?n$
$1?w?10^9$
數(shù)據(jù)保證給出的圖無(wú)重邊和自環(huán)

解題思路

設(shè)f_x為經(jīng)過(guò)x的期望次數(shù)
那么有
$f_1=1$
$f_{eto}=\frac{f_x}{de{g}_x}$
然后用點(diǎn)的期望經(jīng)過(guò)次數(shù)得出邊的期望經(jīng)過(guò)次數(shù)
然后乘上長(zhǎng)度即可

代碼

#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 100010 using namespace std; int n, m, x, y, z, tot, head[N], indeg[N], outdeg[N]; double ans, f[N]; struct rec {int l, to, next; }a[2*N]; void add(int x, int y, int z) {a[++tot].to = y;a[tot].next = head[x];a[tot].l = z;head[x] = tot;outdeg[x]++;indeg[y]++; } void solve() {queue<int>d;d.push(1);f[1] = 1.0;while(!d.empty()){int h = d.front();d.pop();for (int i = head[h]; i; i = a[i].next){f[a[i].to] += f[h] / outdeg[h];//期望經(jīng)過(guò)次數(shù)indeg[a[i].to]--;ans += f[h] /outdeg[h] * a[i].l;//計(jì)算貢獻(xiàn)if (!indeg[a[i].to]) d.push(a[i].to);}}return; } int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= m; ++i){scanf("%d%d%d", &x, &y, &z);add(x, y, z);}solve();printf("%.2lf", ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【期望】路径长度（金牌导航 期望-1）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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