codevs——T2488 绿豆蛙的归宿
2024-08-31 10:52:11
题目描述 Description
随着新版百度空间的上线,Blog宠物绿豆蛙完成了它的使命,去寻找它新的归宿。
给出一个有向无环图,起点为1终点为N,每条边都有一个长度,并且从起点出发能够到达所有的点,所有的点也都能够到达终点。绿豆蛙从起点出发,走向终点。
到达每一个顶点时,如果有K条离开该点的道路,绿豆蛙可以选择任意一条道路离开该点,并且走向每条路的概率为 1/K 。
现在绿豆蛙想知道,从起点走到终点的所经过的路径总长度期望是多少?
输入描述 Input Description
第一行: 两个整数 N M,代表图中有N个点、M条边
第二行到第 1+M 行: 每行3个整数 a b c,代表从a到b有一条长度为c的有向边
输出描述 Output Description
从起点到终点路径总长度的期望值,四舍五入保留两位小数。
样例输入 Sample Input
4 4
1 2 1
1 3 2
2 3 3
3 4 4
样例输出 Sample Output
7.00
数据范围及提示 Data Size & Hint
对于20%的数据 N<=100
对于40%的数据 N<=1000
对于60%的数据 N<=10000
对于100%的数据 N<=100000,M<=2*N
来源:Nescafe 19
因为要无后效性,所以要拓扑排序。处理一个点之前,把它所有连向的点都处理完,所以拓扑排序要倒着来(我是直接反向建图)。
#include <algorithm>
#include <cstdio>
#include <queue> using namespace std; const int N(+);
queue<int>que;
int n,m,u,v,w,rudu[N],chudu[N];
double f[N];
int head[N],edgesum;
struct Edge
{
int from,to,next,dis;
Edge(int from=,int to=,int next=,int dis=) :
from(from),to(to),next(next),dis(dis) {}
}edge[N]; int ins(int from,int to,int dis)
{
edge[++edgesum]=Edge(from,to,head[from],dis);
return head[from]=edgesum;
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
chudu[u]++; rudu[u]++;
ins(v,u,w);
}
for(int i=;i<=n;i++)
if(!rudu[i]) que.push(i);
while(!que.empty())
{
u=que.front();
que.pop();
for(int i=head[u];i;i=edge[i].next)
{
v=edge[i].to;
f[v]+=1.0*(f[u]+edge[i].dis)/chudu[v];
rudu[v]--;
if(!rudu[v]) que.push(v);
}
}
printf("%.2lf",f[]);
return ;
}
最新文章
- iptables的conntrack表满了导致访问网站很慢
- 在现有的图像处理软件中融合dxf格式输出
- u3d avatar部件的理解
- 说说web 2.0生态圈的那些事
- SQL Server 百万级数据提高查询速度的方法
- HDU1198水管并查集Farm Irrigation
- OC基础(24)
- ios开发--旋转、移动、缩放手势实例代码
- Delphi GDI+基本用法总结
- HTTP 500 - 内部服务器错误
- MD5加密 Java源代码
- StringBuilder和string.Format性能对比
- css3波浪形loading动画
- 且看三星刚发布的Smart TV如何窃听你的枕边细语
- Basic Data Structure
- ionic2 获取dom节点
- 【Python61--异常处理】
- 【HANA系列】SAP HANA XS使用JavaScript(JS)调用存储过程(Procedures)
- arduino使用oled显示时间MQ_2温湿度
- Kafka学习之路 (一)Kafka的简介
热门文章
- poj 2914&;&;hdu 3002 全局最小割Stoer-Wagner算法模板
- 开启WIFI
- 解决VTune错误PMU resources currently being used by another profiling tool or process
- 自己定义Android Dialog
- Android学习笔记之ProgressBar案例分析
- ES 處於“initializing”狀態,此時主節點正在嘗試將分片分配到集群中的數據節點。 如果您看到分片仍處於初始化或未分配狀態太長時間,則可能是您的集群不穩定的警告信號。
- nyoj--74--小学生算术(水)
- 基于Apache CXF的Web Service服务端/客户端
- Windows挂载NFS目录权限问题
- 前端面试---常见的web安全及防护原理