首页 > 代码库 > HDU-5001 Walk 2014年鞍山网络赛E题
HDU-5001 Walk 2014年鞍山网络赛E题
依次枚举每个不能走过的点,DP递推下一步情况,求出所有其他点的概率之和即为这个点不会被走过的概率。
#include <iostream> #include <cstdio> #include <queue> #include <algorithm> #include <cstring> #include <cmath> #include <queue> #include <iomanip> #include <vector> #define LL long long #define inf 1<<29 using namespace std; struct node { int u,v; int next; }edge[250000]; int n,m,d; int num; int head[55]; int sum[55]; double dp[11111][55]; void addedge(int u,int v) { edge[num].u=u; edge[num].v=v; edge[num].next=head[u]; head[u]=num++; edge[num].u=v; edge[num].v=u; edge[num].next=head[v]; head[v]=num++; } int main() { int t; int u,v; scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&d); num=0; memset(head,-1,sizeof(head)); memset(dp,0,sizeof(dp)); memset(sum,0,sizeof(sum)); for(int i=0;i<m;i++) { scanf("%d%d",&u,&v); addedge(u,v); sum[u]++; sum[v]++; } for(int i=1;i<=n;i++) { memset(dp,0,sizeof(dp)); for(int ii=1;ii<=n;ii++) { dp[0][ii]=1.0/n; } for(int j=0;j<d;j++) { for(int l=1;l<=n;l++) { if(dp[j][l]!=0&&l!=i) { int len=sum[l]; double temp=dp[j][l]/len; //cout<<temp<<endl; for(int k=head[l];k!=-1;k=edge[k].next) { int v=edge[k].v; dp[j+1][v]+=temp; } } } } double s=0; for(int j=1;j<=n;j++) { if(j!=i) { s+=dp[d][j]; } } printf("%.9f\n",s); } } return 0; }
HDU-5001 Walk 2014年鞍山网络赛E题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。