[HDU5001]Walk
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.
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.
Your answer will be accepted if its absolute error doesn't exceed 1e-5.
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
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define gc getchar()
inline int read(){
int res=;char ch=gc;
while(!isdigit(ch))ch=gc;
while(isdigit(ch)){res=(res<<)+(res<<)+(ch^);ch=gc;}
return res;
}
#undef gc int T, n, m, K;
struct edge{
int nxt, to;
}ed[];
int head[], cnt;
inline void add(int x, int y)
{
ed[++cnt] = (edge){head[x], y};
head[x] = cnt;
}
int deg[];
double f[][]; inline double DP(int cur)
{
memset(f, , sizeof f);
double res = ;
for (int i = ; i <= n ; i ++) f[][i] = (double)(1.0/(double)n);
for (int j = ; j <= K ; j ++)
{
for (int x = ; x <= n ; x ++)
{
if (x == cur) continue;
for (int i = head[x] ; i ; i = ed[i].nxt)
{
int to = ed[i].to;
f[j+][to] += (double)(f[j][x] / (double)deg[x]);
}
}
res += f[j][cur];
}
return res;
} int main()
{
T = read();
while(T--)
{
memset(head, , sizeof head);
memset(deg, , sizeof deg);
cnt = ;
n = read(), m = read(), K = read();
for (int i = ; i <= m ; i ++)
{
int x = read(), y = read();
add(x, y), add(y, x);
deg[x]++, deg[y]++;
}
for (int i = ; i <= n ; i ++)
printf("%.10lf\n", - DP(i));
}
return ;
}
最新文章
- 《HTTP权威指南》大块儿头
- python 聊天室
- opencv 处女作
- Accessorizer的使用说明!
- Oracle GoldenGate Veridata 12.1.3已经发布
- Intellij IDEA 的使用(创建项目、导入项目、同时部署多个项目、JRebel)等常见eclipse、myeclipse换idea必看
- Android-ImageView.ScaleType
- 【转载】React入门-Todolist制作学习
- Java [leetcode 6] ZigZag Conversion
- MorningSale 使用帮助
- python(3)-内置函数
- 动态绑定GridView数据源遇到问题
- cat监控平台环境搭建
- ylb:SQLServer常用系统函数-字符串函数、配置函数、系统统计函数
- .NET MongoDB Driver 2.2 API注释
- MySQL数据库学习三 数据库对象和基本操作
- Codeforces Round #547 (Div. 3)
- js获取时间戳的三种方法
- Testing - 软件测试知识梳理 - 基础概念
- SQL Server聚合函数与聚合开窗函数 (转载)