编程介的小学生 2019-01-06 00:53 采纳率: 19.4%
浏览 299
已采纳

图的遍历+节点访问概率计算,一个数据结构怎么使用C语言实现

Problem Description
I used to think I could be anything, but now I know that I couldn't do anything. So I started traveling.

The nation looks like a connected bidirectional graph, and I am randomly walking on it. It means when I am at node i, I will travel to an adjacent node with the same probability in the next step. I will pick up the start node randomly (each node in the graph has the same probability.), and travel for d steps, noting that I may go through some nodes multiple times.

If I miss some sights at a node, it will make me unhappy. So I wonder for each node, what is the probability that my path doesn't contain it.

Input
The first line contains an integer T, denoting the number of the test cases.

For each test case, the first line contains 3 integers n, m and d, denoting the number of vertices, the number of edges and the number of steps respectively. Then m lines follows, each containing two integers a and b, denoting there is an edge between node a and node b.

T<=20, n<=50, n-1<=m<=n*(n-1)/2, 1<=d<=10000. There is no self-loops or multiple edges in the graph, and the graph is connected. The nodes are indexed from 1.

Output
For each test cases, output n lines, the i-th line containing the desired probability for the i-th node.

Your answer will be accepted if its absolute error doesn't exceed 1e-5.

Sample Input
2
5 10 100
1 2
2 3
3 4
4 5
1 5
2 4
3 5
2 5
1 4
1 3
10 10 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
4 9

Sample Output
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.6993317967
0.5864284952
0.4440860821
0.2275896991
0.4294074591
0.4851048742
0.4896018842
0.4525044250
0.3406567483
0.6421630037

  • 写回答

1条回答 默认 最新

  • threenewbee 2019-11-30 23:40
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 qteasy 运行前进中
  • ¥15 我想通过python处理sybase IQ库的一些数据,但是不知道sybase IQ库怎么连接,之前连接都是用linux上的 dbisql
  • ¥15 安装llama-cpp-python==0.1.83失败
  • ¥20 管道轴向耦合水击问题
  • ¥60 补全networkx TODO部分。
  • ¥15 有内推吗,云计算linux运维方向
  • ¥30 sort cuteSV.vcf by bcftools用IGV可视化出现报错
  • ¥100 SOS!对STK中导出的天体图像进行质心提取有没有人做过啊
  • ¥15 python 欧式距离
  • ¥15 遗传算法解决有工序顺序约束的大规模FJSP问题