P6154 游走

本文主要是介绍P6154 游走，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给出有向无环图，可能存在重边，每条边的边权均为1，问从其中随机等可能的挑选一条路径，问挑选出边的长度的期望是多少

思路：对于结果即为所有路径的长度总和除以总路径数量，而我们不容易直接找出所有路径然后计算长度总和，这题为有向无环图，所以我们可以通过拓扑来转移出以每个点为结尾的所所有路径的长度总和以及路径条数，正因为只有将所有一个点之前的所有点的状态全部得出之后，才能用这个点的状态来继续向下转移，所以可证拓扑的正确性

这里我们设len[i]代表以i为结尾的所有路径的长度总和,num[i]代表以i为结尾的路径数量

则对于一个队列中的可转移点u的所有临点v，num[v]+=num[u],len[v]+=len[u]+num[u]，注意第二个转移方程+num[u]的原因是u到v的那条边， 总共会有num[u]条边会经过

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=1e5+10,mod=998244353;
int du[N],len[N],num[N];
int n,m;
vector<int> g[N];
int qmi(int a,int b,int p)
{int res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;
}
void top()
{queue<int> q;for(int i=1;i<=n;i++)if(du[i]==0)q.push(i);while(q.size()){int u=q.front();// cout<<u<<endl;q.pop();for(auto v:g[u]){num[v]=(num[v]+num[u])%mod;len[v]=(len[v]+len[u]+num[u])%mod;if(--du[v]==0)q.push(v);}}
}
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++)num[i]=1;for(int i=0;i<m;i++){int u,v;cin>>u>>v;g[u].pb(v);du[v]++;}top();int reslen=0,resnum=0;for(int i=1;i<=n;i++){reslen=(reslen+len[i])%mod;resnum=(resnum+num[i])%mod;}cout<<reslen*qmi(resnum,mod-2,mod)%mod<<endl;
}
signed main()
{Mirai;int T=1;//cin>>T;while(T--){solve();}
}

这篇关于P6154 游走的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---