绿豆蛙的归宿
题目背景
随着新版百度空间的上线，Blog 宠物绿豆蛙完成了它的使命，去寻找它新的归宿。
题目描述
给出张 \(n\) 个点 \(m\) 条边的有向无环图，起点为 \(1\)，终点为 \(n\)，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。
绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果该节点有 \(k\) 条出边，绿豆蛙可以选择任意一条边离开该点，并且走向每条边的概率为 \(\frac{1}{k}\) 。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？
输入格式
输入的第一行是两个整数，分别代表图的点数 \(n\) 和边数 \(m\)。
第 \(2\) 到第 \((m + 1)\) 行，每行有三个整数 \(u, v, w\)，代表存在一条从 \(u\) 指向 \(v\) 长度为 \(w\) 的有向边。
输出格式
输出一行一个实数代表答案，四舍五入保留两位小数。
样例 #1
样例输入 #1
4 4
1 2 1
1 3 2
2 3 3
3 4 4
样例输出 #1
7.00
提示
数据规模与约定
- 对于 \(20\%\) 的数据，保证 \(n \leq 10^2\)。
- 对于 \(40\%\) 的数据，保证 \(n \leq 10^3\)。
- 对于 \(60\%\) 的数据，保证 \(n \leq 10^4\)。
- 对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 10^5\)，\(1 \leq m \leq 2 \times n\)，\(1 \leq u, v \leq n\)，\(1 \leq w \leq 10^9\)，给出的图无重边和自环。
这题要求概率期望
期望的线性
\(E(aX+bY)=aE(X)+bE(Y)\)
因为是有向无环图
期望概率DP
一般期望的问题，起点是唯一的，终点一般是不唯一的，但这题如果建正图就相反了，最方便的是建反图，所以我们递推时候，可以倒推
\(F[i]从i跳到u的期望概率\)
\(E(1/k(w_1+x_1)+1/k(w_2+x_2)+...)\)
可以转换为\(1/k(w_1+E(x_1))+1/k(w_2+E(x_2))...\)
所以\(F[to]=\sum_{i=1}^k1/k(F[u]+w_{to})\)
现在基本不用担心栈的问题,CCF把栈的空间开到了内存限制(看题目),但是数组开了多大，就会占用多少空间,栈也会用空间
-std=c++2a -Wl,--stack=100000000
点击查看代码
#include <bits/stdc++.h>
#define ll long long
//#define int long long
#define rint int
#define mk make_pair
#define pb push_back
#define lid (rt<<1)
#define rid (rt<<1|1)
using namespace std;
const int N = 3e5+5;
int cnt,n,m,head[N];
struct Edge
{
int u,to,w,next;
}edge[N*2];
void add(int u,int v,int w)
{
edge[++cnt].u=u;
edge[cnt].to=v;
edge[cnt].next=head[u];
edge[cnt].w=w;
head[u]=cnt;
}
int in[N];double f[N];int deg[N];
void topsort()
{
queue <int> q;
q.push(n);
while(!q.empty())
{
int u=q.front();q.pop();
// cout<<u<<endl;
for(int i=head[u];i;i=edge[i].next)
{
int to=edge[i].to;
f[to]+=(f[u]+edge[i].w)/deg[to];
in[to]--;
if(!in[to])
{
q.push(to);
}
}
}
}
int main()
{
// freopen("P4316_2.in","r",stdin);
cin>>n>>m;
int u,v,w;
for(int i=1;i<=m;i++)
{
cin>>u>>v>>w;
add(v,u,w);
in[u]++;deg[u]++;
}
topsort();
printf("%.2lf",f[1]);
// cout<<f[n]<<endl;
return 0;
}
当然也可建正图,不过有概率
