【河南省第九届ACM程序设计大赛 信道安全 +zzulioj 1925 信道安全 +邻接表 +队列 】
发布日期:2021-11-04 12:59:36
浏览次数:16
分类:技术文章
本文共 1902 字,大约阅读时间需要 6 分钟。
Description
Alpha 机构有自己的一套网络系统进行信息传送。情报员 A 位于节点 1,他准备将一份情报
发送给位于节点 n 的情报部门。可是由于最近国际纷争,战事不断,很多信道都有可能被遭到监
视或破坏。
经过测试分析,Alpha 情报系统获得了网络中每段信道安全可靠性的概率,情报员 A 决定选
择一条安全性最高,即概率最大的信道路径进行发送情报。
你能帮情报员 A 找到这条信道路径吗?
Input
第一行: T 表示以下有 T 组测试数据 ( 1≤T ≤8 )
对每组测试数据:
第一行: n m 分别表示网络中的节点数和信道数 (1<=n<=10000,1<=m<=50000)
接下来有 m 行, 每行包含三个整数 i,j,p,表示节点 i 与节点 j 之间有一条信道,其信
道安全可靠性的概率为 p%。 ( 1<=i, j<=n 1<=p<=100)
Output
每组测试数据,输出占一行,一个实数 即情报传送到达节点 n 的最高概率,精确到小数点后
6 位。
Sample Input
1
5 7 5 2 100 3 5 80 2 3 70 2 1 50 3 4 90 4 1 85 3 1 70Sample Output
61.200000
HINT
Source
河南省第九届大学程序设计竞赛
#include#include #include #include using namespace std;struct node{ int fx,fy,next; double vl;}st[100022];int vis[10011],head[100011],n,m,num;double dis[10011];void DFS(){ queue q; int i,j,ka; double ans; memset(vis,0,sizeof(vis)); memset(dis,0,sizeof(dis)); dis[1] = 1.0; vis[1] = 1; q.push(1); while(!q.empty()) { int pl = q.front(); q.pop(); vis[pl] = 0; // 释放改点 for(int i = head[pl] ; i != -1 ; i = st[i].next) { int py = st[i].fy; if(dis[py] < dis[pl] * st[i].vl) { dis[py] = dis[pl] * st[i].vl; if(!vis[py]) { vis[py] = 1; // 标记改点 q.push(py); } } } } printf("%.6lf\n",dis[n] * 100);}void add(int px,int py,double va){ st[num].fx = px; st[num].fy = py; st[num].vl = va; st[num].next = head[px]; head[px] = num++;}int main(){ int T,a,b,i,j; double val; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); num = 0 ; memset(head,-1,sizeof(head)); while(m--) { scanf("%d%d%lf",&a,&b,&val); val /= 100; add(a,b,val); add(b,a,val); } DFS(); } return 0;}
转载地址:https://blog.csdn.net/WYK1823376647/article/details/52548961 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年04月25日 10时13分12秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Java 常见的 30 个误区与细节
2019-04-28
干货|基于 Spring Cloud 的微服务落地
2019-04-28
WEB攻击手段及防御第2篇-SQL注入
2019-04-28
WEB攻击手段及防御第3篇-CSRF
2019-04-28
WEB攻击手段及防御-扩展篇
2019-04-28
spring bean初始化及销毁你必须要掌握的回调方法。
2019-04-28
mysql语句性能开销检测profiling详解
2019-04-28
hashCode到底有什么用?
2019-04-28
设计模式之动态代理模式实战
2021-07-01
设计模式之静态代理模式实战
2021-07-01
作为架构师,你必需要搞清楚的概念:POJO、PO、DTO、DAO、BO、VO
2021-07-01
mysql查询优化explain命令详解
2021-07-01
常用加密算法解析
2021-07-01
设计模式之单例模式实践
2021-07-01
彻底理解正向代理和反向代理
2021-07-01
一次频繁Full GC的排查过程,根源居然是它...
2021-07-01
Unicode与UTF-8的区别
2021-07-01
最长回文子串(Longest Palindromic Substring)
2021-07-01
Windows 通过 SecureCRT 8.x 上传文件到Linux服务器
2021-07-01
Spring MVC的GET与POST请求url-pattern坑
2021-07-01