给出一个有向无环图，起点为1终点为N，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。 现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？

咕咕咕了大量知识点的总结后，写一篇题的解题报告

在被lyd的大量BT例题虐杀后，看到这么一道题，那是激动，直接秒了（假假

题解：

f[x]表示以x为起点走到终点的路径总长度期望

设从x连出去的边y1, y2, y3, ..., yk, 路径长度为z1, z2, z3, ..., zk

很容易想到式子为:

f[x] = 1/k * Σ(f[yi]+zi)(1<=i<=k)

意会一下觉得需要建一个反图

然后在反图上执行拓扑排序，在拓扑排序的同时计算期望

1 #include
     
       2 #define ll long long 3 #define ld long double 4 #define uint unsigned int 5 using namespace std; 6 const int maxn = 100010, maxm = 200010; 7 struct shiki { 8     int y, net, val; 9 }e[maxm << 1];10 int lin[maxn], len = 0;11 int n, m;12 int K[maxn], in[maxn];13 double f[maxn];14 queue
      
        q;15 16 inline int read() {17     int x = 0, y = 1;18     char ch = getchar();19     while(!isdigit(ch)) {20         if(ch == '-') y = -1;21         ch = getchar();22     }23     while(isdigit(ch)) {24         x = (x << 1) + (x << 3) + ch - '0';25         ch = getchar();26     }27     return x * y;28 }29 30 inline void insert(int xx, int yy, int v) {31     e[++len].y = yy;32     e[len].net = lin[xx];33     e[len].val = v;34     lin[xx] = len;35 }36 37 int main() {38 //    freopen("test.in", "r", stdin);39 //    freopen("test.out", "w", stdout);40     n = read(), m = read();41     for(register uint i = 1; i <= m; ++i) {42         int x = read(), y = read(), z = read();43         insert(y, x, z);44         K[x]++, in[x]++;//反图上连向x的边数和反图上x的入度，也就是原图x连出的边数和x的出度 45     }46     q.push(n);47     while(!q.empty()) {48         int k = q.front(); q.pop();49         for(int i = lin[k]; i; i = e[i].net) {50             int to = e[i].y;51             f[to] += (f[k] + e[i].val) / K[to];52             in[to]--;53             if(!in[to]) q.push(to);54         }55     }56     printf("%0.2f", f[1]);57     return 0;58 }