题目描述
给出张 n 个点 m 条边的有向无环图，起点为 1，终点为
n，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。
绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果该节点有
k
条出边，绿豆蛙可以选择任意一条边离开该点，并且走向每条边的概率为 \(\frac{1}{k}\)
。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？
输入格式
输入的第一行是两个整数，分别代表图的点数 n 和边数
m。
第 2 到第(m+1) 行，每行有三个整数 u, v,
w，代表存在一条从u 指向v 长度为w
的有向边。
输出格式
输出一行一个实数代表答案，四舍五入保留两位小数。
输入输出样例
输入 #1
| 4 4
1 2 1
1 3 2
2 3 3
3 4 4
|
输出 #1
说明/提示
数据规模与约定
- 对于100% 的数据，保证
1≤n≤105，1≤m≤2×n，1≤u,v≤n，1≤w≤109，给出的图无重边和自环。
思路
一般的期望dp都可以考虑正推或逆推，更关键的是要得出递推公式
初状态已知就正推，末状态已知就正推
考虑到此题的图的结构我们使用拓扑序加bfs来保证dp更新的顺序正确
正推
设dp[i]表示从1到i的期望路径长度
g[i]表示从1到i的概率
从i出发，有k条路径，分别到达j1,j2,...,jn,路程为w1，w2,...,wn
则可得\(dp[j]=(dp[i]+w_i\times
g[i]/k)\) , \(g[j]=g[i]/k\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N=1e5+10;
struct node{
int v,w;
};
double dp[N],g[N];
int in[N],out[N];
vector<node>t[N];
void bfs(int u){
g[1]=1;
queue<int>q;
q.push(1);
while(!q.empty()){
u=q.front();
q.pop();
for(auto v:t[u]){
dp[v.v]+=1.0*(dp[u]+g[u]*v.w)/t[u].size();
g[v.v]+=1.0*g[u]/t[u].size();
in[v.v]--;
if(in[v.v]==0)q.push(v.v);
}
}
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,c;
cin>>u>>v>>c;
t[u].push_back({v,c});
in[v]++;
out[u]++;
}
bfs(1);
printf("%.2f",dp[n]);
return 0;
}
|
逆推
dp[i]表示i到终点经过的路径的期望长度
从i出发，有k条路径，分别到达j1,j2,...,jn,路程为w1，w2,...,wn
\(dp[i]=\frac{1}{k}\times(dp[j_1]+w_1)+\frac{1}{k}\times(dp[j_2]+w_2)+...+\frac{1}{k}\times(dp[j_k]+w_k)=\sum_{i=1}^kdp[j_i]+w_i\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N=1e5+10;
struct node{
int v,w;
};
double dp[N],g[N];
int in[N],siz[N];
vector<node>t[N];
void bfs(int u){
queue<int>q;
q.push(u);
while(!q.empty()){
u=q.front();
q.pop();
for(auto v:t[u]){
dp[v.v]+=1.0*(dp[u]+v.w)/siz[v.v];
in[v.v]--;
if(in[v.v]==0)q.push(v.v);
}
}
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,c;
cin>>u>>v>>c;
t[v].push_back({u,c});
in[u]++;
siz[u]++;
}
bfs(n);
printf("%.2f",dp[1]);
return 0;
}
|