题意：给出一幅有向无环图，保证只有1入度为0，n出度为0，求问一个机器人从1出发，每天等概率的走到相邻点或者留在原地，问到达n点的代价。每天的代价都不一样，就是天数（第x天走一步的代价就是x）。
思路：设出度每个点的选择情况为$cnt[i]$，即出度加1.
由于每天的代价和天数有关，所以应该要想到，可以先算出天数的期望。这样就可以得到每个点的代价，再算总的代价期望。
把一道题拆成两题，简单求解。
$dp[u]=dp[u]*frac{1}{cnt[u]}+frac{1}{cnt[u]}* sum dp[v]+1$
移项可得 $dp[u]=frac{1}{cnt[u]-1}sum dp[v]+frac{k}{k-1}$
然后求f
$f[u]=frac{1}{cnt[u]}f[u]+frac{1}{cnt[u]}*sum f[v] +dp[u]$
$f[u]=frac{1}{cnt[u]-1}sum f[v]+frac{k}{k-1}*dp[u]$
然后按照拓扑序的逆序来dp。
#pragma GCC optimize (2) #pragma G++ optimize (2) #pragma comment(linker, "/STACK:102400000,102400000") #include<bits/stdc++.h> #include<unordered_map> #define rep(i,a,b) for(int i=a;i<=b;++i) #define dep(i,b,a) for(int i=b;i>=a;--i) #define clr(a,b) memset(a,b,sizeof(a)) #define pb push_back #define pii pair<int,int > using namespace std; typedef long long ll; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int maxn=400010; const int inf=0x3f3f3f3f; int n,m; double dp[maxn],f[maxn]; double cnt[maxn]; int to[maxn],tot,dep[maxn]; vector<int >ve[maxn]; void topo(){ queue<int >q; q.push(1); tot=0; while(!q.empty()){ int u=q.front(); q.pop(); to[++tot]=u; for(auto &v:ve[u]){ dep[v]--; if(dep[v]==0){ q.push(v); } } } } int main(){ int T; cin>>T; while(T--){ scanf("%d%d",&n,&m); rep(i,1,n){ cnt[i]=1; dp[i]=0; f[i]=0; dep[i]=0; ve[i].clear(); } rep(i,1,m){ int u,v; scanf("%d%d",&u,&v); ve[u].push_back(v); cnt[u]++; dep[v]++; } topo(); for(int i=tot-1;i>0;--i){ int u=to[i]; double k=cnt[u]; dp[u]=k/(k-1); for(auto &v:ve[u]){ dp[u]+=(dp[v])/(k-1); } } for(int i=tot-1;i>0;--i){ int u=to[i]; double k=cnt[u]; f[u]=k/(k-1)*dp[u]; for(auto &v:ve[u]){ f[u]+=(f[v])/(k-1); } } printf("%.2f ",f[1]); } }