HDU 5001
2024-08-27 04:42:19
http://acm.hdu.edu.cn/showproblem.php?pid=5001
每次去掉要算的点,求出到达其他点的概率,就是不能到达这个点的概率
开始想去算到达这个点的概率,再去减,不过这种方法证实是不对的,重复走的情况会重复计算
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std ; double dp[][] ;
int mp[][] ;
int cnt[] ;
int main()
{
int T ;
scanf("%d",&T) ;
while(T--)
{
int n,m,d ;
scanf("%d%d%d",&n,&m,&d) ;
memset(mp,,sizeof(mp)) ;
for(int i= ;i<m ;i++)
{
int a,b ;
scanf("%d%d",&a,&b) ;
mp[a][b]=mp[b][a]= ;
}
memset(cnt,,sizeof(cnt)) ;
for(int i= ;i<=n ;i++)
{
for(int j= ;j<=n ;j++)
{
if(i==j)continue ;
if(mp[i][j])cnt[i]++ ;
}
}
for(int v= ;v<=n ;v++)
{
for(int i= ;i< ;i++)
for(int j= ;j< ;j++)
dp[i][j]=0.0 ;
for(int i= ;i<=n ;i++)
dp[i][]=1.0/n ;
for(int i= ;i<=d ;i++)
{
for(int j= ;j<=n ;j++)
{
if(v==j)continue ;
for(int h= ;h<=n ;h++)
{
if(mp[h][j])dp[h][i]+=dp[j][i-]*(1.0/cnt[j]) ;
}
}
}
double ans=0.0 ;
for(int i= ;i<=n ;i++)
{
if(v==i)continue ;
ans+=dp[i][d] ;
}
printf("%.6lf\n",ans) ;
}
}
return ;
}
最新文章
- swift学习笔记4——扩展、协议
- Android获取服务器Json字符串并显示在ListView上面
- Java当中的反射
- Autorun.inf文件(2):改变硬盘分区图标
- 一个python线程池的源码解析
- Unity3d 用NGUI制作做新手引导的思路
- 请确认 <;Import>; 声明中的路径正确,且磁盘上存在该文件。
- function format_number(srcNumber, n) {
- Using SharePoint 2010 dialogs
- 【 java版坦克大战--事件处理】 让坦克动起来--事件处理的准备
- HTTP学习目录
- 一个js的动画,以前以为只有flash可以实现
- springboot 的部分细节
- junit测试
- select中想要加a链接 并且新窗口打开
- WPF 开发备忘录
- Apache Struts2高危漏洞(S2-057CVE-2018-11776)
- HTML第三章总结
- 最简单的iOS网络请求
- CNN 中, 1X1卷积核到底有什么作用