hdu5001(概率dp)
2024-08-25 14:36:00
题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=5001
题意:一个人随即从一个点出发,到达邻接点的概率相同,求出走d步都不会到达1~n点的每一点i的概率。
分析:每次删掉i点去计算d步后到达其他点的概率,加起来的都是没有到达i点的概率。
一开始算出x步到达每点的概率,然后d步后(1-dp[x][i])^d,错了,因为算每点到达的概率时已经算了到达i点时的概率了。
网络赛时这道水题做不出,好殇。。。。。
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-9
#define N 100010
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
double dp[][];
vector<int>g[];
int main()
{
int t,n,m,d;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&d);
for(int i=;i<=n;i++)g[i].clear();
for(int i=;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=;i<=n;i++)
{
FILL(dp,);
for(int j=;j<=n;j++)
if(j!=i)dp[][j]=1.0/n;
for(int x=;x<=d;x++)
{
for(int j=;j<=n;j++)
{
if(i==j)continue;
for(int k=,sz=g[j].size();k<sz;k++)
{
int v=g[j][k];
if(v!=i)dp[x][v]+=dp[x-][j]/sz;
}
}
}
double res=;
for(int j=;j<=n;j++)
if(i!=j)res+=dp[d][j];
printf("%.10lf\n",res);
}
}
}
最新文章
- JavaSE高级之集合类
- 微信小程序小技巧系列《一》幻灯片,tab导航切换
- HTTP 2.0与HTTP 1.1区别
- jquery的$.ajax async使用详解
- JGibbLDA、GibbsLDA++问题解决
- Java_数组
- oracle中一个字符串包含另一个字符串中的所有字符
- 解决 ko mapping 数组无法添加新对象的问题
- linux之history
- Delphi 和 DFM
- cocos2dx Sprite的多种创建方法
- JAVA语法题
- Windows7下安装IIS
- 在C++遇到有些关键字或者函数被弃用的情况
- XXE漏洞学习
- 我的 FPGA 学习历程(04)—— 练习 verilog 硬件描述语言
- 常用的HTML模板(转载)
- 一个JavaBean和DTO转换的优秀案例
- Oracle中字符串连接的实现方法
- 跟厂长学PHP7内核(八):深入理解字符串的实现
热门文章
- CSU1664: 防水堤坝
- EasyUI - Layout 布局控件
- 基于visual Studio2013解决C语言竞赛题之1077大数相加
- paip.php 配置ZEND DEBUGGER 断点调试for cli..
- ARC内存使用注意事项
- 微软推荐的130道ASP.NET常见面试题及答案
- Java中@Deprecated、@SupressWarning、@Override的作用
- Direct UI 思想阐述(好多相关文章)
- gcc中__attribute__ ((constructor(101)))做成.a库成功链接
- 使用malloc分别分配2KB,6KB的内存空间,打印指针地址