绿豆蛙的归宿【牛客tracker 每日一题】

绿豆蛙的归宿时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述给定一张由N NN个点、M MM条边组成的有向无环连通图起点编号为1 11终点编号为N NN。每条边( u , v ) (u,v)(u,v)具有非负长度w u , v w_{u,v}wu,v​。当绿豆蛙到达顶点u uu时若该点存在k kk条出边则它会以相同的概率1 k \frac{1}{k}k1​选择其中一条边离开该点。请计算绿豆蛙从起点1 11出发到达终点N NN的路径总长度的期望值。输入描述第一行输入两个整数N , M ( 2 ≦ N ≦ 10 5 , 1 ≦ M ≦ 2 × N ) N,M(2≦N≦10^5, 1≦M≦2×N)N,M(2≦N≦105,1≦M≦2×N)分别表示点数与边数。接下来M MM行每行输入三个整数a , b , c ( 1 ≦ a ≠ b ≦ N , 0 ≦ c ≦ 10 4 ) a,b,c(1≦a≠b≦N, 0≦c≦10^4)a,b,c(1≦ab≦N,0≦c≦104)表示存在一条从a aa指向b bb、长度为c cc的有向边。保证整张图为有向无环图且从1 11可以到达N NN。输出描述输出一个实数表示期望路径长度四舍五入保留两位小数。示例1输入4 4 1 2 1 1 3 2 2 3 3 3 4 4输出7.00解题思路本题核心是有向无环图期望DP拓扑排序求解路径长度期望。定义dp[u]表示从节点u走到终点N的路径期望长度终点dp[N]0。对于有k条出边的节点u期望公式为d p [ u ] ∑ d p [ v ] w k dp[u] \sum \frac{dp[v]w}{k}dp[u]∑kdp[v]w​。由于图是有向无环图采用逆拓扑序从终点向起点递推保证计算每个节点时其后继节点的期望已求出。先建图统计出度完成拓扑排序后逆序遍历计算所有dp值最终输出dp[1]并保留两位小数。算法时间复杂度O ( N M ) O(NM)O(NM)完美适配N ≤ 10 5 N \le 10^5N≤105的大数据规模。总结核心逻辑在D A G DAGDAG上使用动态规划计算期望依托终点的已知状态逆序递推。关键操作构建有向图拓扑排序确定计算顺序按期望公式递推求解。效率保障线性时间复杂度无冗余计算高效处理大规模图的期望计算。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e510;constll p1e97;constll INF1e18;constll M2e310;vectorpllarr[N];intmain(){ll n,m,a,b,c;cinnm;for(ll i1;im;i){cinabc;arr[a].push_back({b,c});}doubleans0;queuepllq;q.push({1,1});while(q.size()){autonowq.front();q.pop();for(autoi:arr[now.first]){ansi.second/(arr[now.first].size()*now.second*1.0);q.push({i.first,now.second*arr[now.first].size()});}}printf(%.2f,ans);return0;}