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.
# include<iostream>
# include<cstdio>
# include<vector>
# include<cstring>
# include<algorithm>
using namespace std;
vector<int>v[55];
int n,m,d,vis[10005][55];
double dp[10005][55];
void solve()
{
for(int i=1;i<=n;++i){
memset(dp,0,sizeof(dp));
for(int j=1;j<=n;++j)
dp[0][j]=1.0/n;
for(int j=1;j<=d;++j){
for(int start=1;start<=n;++start){
if(i==start)
continue;
int l=v[start].size();
for(int k=0;k<l;++k)
dp[j][v[start][k]]+=dp[j-1][start]*1.0/l;
}
}
double ans=0.0;
for(int j=1;j<=n;++j)
if(j!=i)
ans+=dp[d][j];
printf("%.10lf\n",ans);
}
}
int main()
{
int T,a,b;
vector<int>::iterator it;
scanf("%d",&T);
while(T--)
{
memset(vis,0,sizeof(vis));
scanf("%d%d%d",&n,&m,&d);
for(int i=1;i<=n;++i)
v[i].clear();
while(m--)
{
scanf("%d%d",&a,&b);
it=find(v[a].begin(),v[a].end(),b);
if(it==v[a].end())
v[a].push_back(b);
it=find(v[b].begin(),v[b].end(),a);
if(it==v[b].end())
v[b].push_back(a);
}
solve();
}
return 0;
}