P4316 绿豆蛙的归宿

题意：给出一个有向无环图，对于每个点，一共有k条出边，则选择每条边的概率相等，都为1/k，问从点1走到点n的期望路径长度

思路：有向无环图，考虑拓扑，本题不同于P6154 游走，P6154这题是所有路径的概率相等，而本题仅仅只是对于每个点选择出边的时候每条出边的概率相同，所以显然每条路径的概率并不相同，所以我们不能总体对路径进行分析，本题需要对每条边进行分析，我们可以求出每条边的期望选择次数，再乘边权求和即可得到结果

对于每条边，期望次数即为这条边的起点的期望次数+1/k[i]

对于每个点，期望次数即为所有以这个点为临点的其他点的（期望次数+1/k[i]）的和

Accode：

#include<bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
#define INFF 0x3f3f3f3f3f3f3f3f
#define int long long
#define fix fixed<<setprecision
#define pb push_back
#define Mirai ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
typedef pair<int,int> pii;
const int N=2e5+10;
int du[N],w[N];
double cnt[N],f[N];
double dp[N];
vector<pii> g[N];
int n,m;
void top()
{
    queue<int> q;
    q.push(1);
    cnt[1]=1;
    while(q.size())
    {
        int u=q.front();
        q.pop();
        for(auto [v,wid]:g[u])
        {
            cnt[v]+=cnt[u]/g[u].size();
            f[wid]+=cnt[u]/g[u].size();
            if(--du[v]==0)q.push(v);
        }
    }
}
void solve()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int u,v;
        cin>>u>>v>>w[i];
        g[u].pb({v,i});
        du[v]++;
    }
    top();
    double res=0;
    for(int i=0;i<m;i++)
    {
        res+=w[i]*f[i];
    }
    cout<<fix(2);
    cout<<res<<endl;
}
signed main()
{
    Mirai;
    int T=1;
    //cin>>T;
    while(T--)
    {
        solve();
    }
}