算法竞赛进阶指南，182 页，概率数学期望
本题要点：
1、dis[x] 表示点x到终点所有经过的路径的期望长度。如果从点x出发有k条边，
分别到达 y[1], y[2], …, y[k], 边长分别是 z[1], z[2], …, z[k]那么
dis[x] = 1 / k * sum{dis[y[1]] + z[1], dis[y[2]] + z[2], …, dis[y[k]] + z[k]}
显然 dis[n] = 0;
2、建立原来图的反向图，求反图的拓扑排序，顺便计算每一点的 dis[i]。
我要评论#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int MaxN = 100010, MaxM = 200010;
int ver[MaxM], edge[MaxM], Next[MaxM], head[MaxN];
int in_deg[MaxN], deg[MaxN];
int n, m, tot;
double dis[MaxN];
queue<int> q; //拓扑排序
void add(int x, int y, int z)
{
ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
}
int main()
{
int x, y, z;
scanf("%d%d", &n, &m);
for(int i = 0; i < m; ++i)
{
scanf("%d%d%d", &x, &y, &z);
add(y, x, z); //建立反图
in_deg[x]++, deg[x]++; //in_deg 用于拓扑排序， deg[x] 表示点x 的入度总数
}
q.push(n);
while(q.size())
{
int y = q.front(); q.pop();
for(int i = head[y]; i; i = Next[i])
{
int x = ver[i];
dis[x] += (dis[y] + edge[i]) / deg[x];
in_deg[x]--;
if(!in_deg[x])
{
q.push(x);
}
}
}
printf("%.2lf\n", dis[1]);
return 0;
}
/*
4 4
1 2 1
1 3 2
2 3 3
3 4 4
*/
/*
7.00
*/
本文地址：https://blog.csdn.net/qq_38232157/article/details/107347518
如对本文有疑问， 点击进行留言回复！！
Postgresql结合postgis使用java的JDBC连接
网友评论