当前位置: 首页 > news >正文

P2047 [NOI2007] 社交网络

Portal.

观察到数据范围 n ≤ 100 n\leq 100 n100,考虑用 Floyd。

在 Floyd 更新最短路的过程中,如果以当前结点为中转点的路径更新过,那么可以累加答案;否则,更新最短路径并重置答案。

统计答案时,枚举中转点判断累加即可。

#include <bits/stdc++.h>
using namespace std;
#define int long longint f[105][105],C[105][105];
double I[105];signed main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=1e9;for(int i=1,a,b,c;i<=m;i++) cin>>a>>b>>c,f[a][b]=f[b][a]=c,C[a][b]=C[b][a]=1;for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j&&j!=k&&i!=k){if(f[i][j]==f[i][k]+f[k][j]) C[i][j]+=C[i][k]*C[k][j];else if(f[i][j]>f[i][k]+f[k][j]) f[i][j]=f[i][k]+f[k][j],C[i][j]=C[i][k]*C[k][j];}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j&&j!=k&&k!=i&&f[i][j]==f[i][k]+f[k][j]) I[k]+=((double)C[i][k]*C[k][j])/C[i][j];for(int i=1;i<=n;i++) printf("%.3lf\n",I[i]);return 0;
}

相关文章:

P2047 [NOI2007] 社交网络

Portal. 观察到数据范围 n ≤ 100 n\leq 100 n≤100&#xff0c;考虑用 Floyd。 在 Floyd 更新最短路的过程中&#xff0c;如果以当前结点为中转点的路径更新过&#xff0c;那么可以累加答案&#xff1b;否则&#xff0c;更新最短路径并重置答案。 统计答案时&#xff0c;枚…...

线性表的顺序存储

1.创建&#xff1a;实质是对data与length的修改 //定义一个线性表 typedef struct {int data[MaxSize];//存储线性表的元素 int length;//线性表的长度 }SqList; //新建一个表 void create(SqList &l){//传入地址才可以对其值进行改变 printf("请输入线性表的长度&…...

ChinaSoft 论坛巡礼 | 安全攸关软件的智能化开发方法论坛

2023年CCF中国软件大会&#xff08;CCF ChinaSoft 2023&#xff09;由CCF主办&#xff0c;CCF系统软件专委会、形式化方法专委会、软件工程专委会以及复旦大学联合承办&#xff0c;将于2023年12月1-3日在上海国际会议中心举行。 本次大会主题是“智能化软件创新推动数字经济与社…...

采用XML作为GUI描述语言

设计方案采用XML作为GUI描述语言的机制主要包括以下几个方面: 模型定义:使用XML定义GUI组件的模型,包括组件的名称、类型、属性、事件等。布局管理:使用XML定义GUI组件的布局,包括组件之间的相对位置、大小、对齐方式等。数据绑定:使用XML定义GUI组件的数据绑定方式,包括数据来…...

rust入门基础案例:猜数字游戏

案例出处是《Rust权威指南》&#xff0c;书中有更加详细的解释。从这个例子中&#xff0c;我们可以了解到 rust 的两个操作&#xff1a; 如何从控制台读取用户输入rust 如何生成随机数 代码格式化 编译器可在保存时对代码做格式化处理&#xff0c;底层调用 rustfmt 来实现&a…...

vue-cli5.0.x优雅降级,配置项目兼容旧版浏览器

兼容低版本谷歌浏览器 vue-cli5.0.x脚手架下的&#xff0c;如何降低项目版本以适用于底版本的浏览器。 直接使用默认配置打包部署出来的项目再40&#xff0c;60、70版本的谷歌浏览器跑不起来&#xff0c;蓝屏或者浏览器白屏一般这种情况都需要通过Babel去做转换&#xff0c;我…...

关于RabbitMQ的小总结

问题&#xff1a;消息在转换机无法被路由 发布确认高级作用在生产者发送到转换机&#xff0c;回退消息作用在消息在转换机无法被路由的情况&#xff08;消息无法路由的意思是&#xff0c;消息在转换机没有匹配到对应的队列&#xff09;&#xff0c;进行消息回退&#xff0c;打…...

webgoat靶场攻关

A&#xff08;5&#xff09; Broken Access Control Insecure Direct Object References 直接对象引用 直接对象引用是指应用程序使用客户端提供的输入来访问数据和对象。 例子 使用 GET 方法的直接对象引用示例可能如下所示 https://some.company.tld/dor?id12345 https…...

BEV-YOLO 论文学习

1. 解决了什么问题&#xff1f; 出于安全和导航的目的&#xff0c;自驾感知系统需要全面而迅速地理解周围的环境。目前主流的研究方向有两个&#xff1a;第一种传感器融合方案整合激光雷达、相机和毫米波雷达&#xff0c;和第二种纯视觉方案。传感器融合方案的感知表现鲁棒&am…...

C++可以使用负数作为下标索引

今天碰到一个题目&#xff0c;写bfs写炸了&#xff0c;发现好像数组越界&#xff0c;但是却没有报错&#xff0c;而是被边界检查拦截了 导致死循环了&#xff1f;&#xff1f;&#xff1f; ps:所以写边界问题&#xff0c;首要的就是对边界进行检查&#xff0c;不检查越界之后…...

react+canvas实现横跨整个页面的动态的波浪线(贝塞尔曲线)

本来写这个特效 我打算用css实现的&#xff0c;结果是一波三折&#xff0c;我太难了&#xff0c;最终没能用css实现&#xff0c;转战了canvas来实现。来吧先看效果图 当然这个图的波浪高度、频率、位置、速度都是可调的&#xff0c;请根据自己的需求调整&#xff0c;如果你讲波…...

峰回网关数采PLC

1.网络配置 例如&#xff1a;plc地址是192.168.1.56 1.访问网关 峰回网关默认网关地址 192.168.3.18&#xff0c;或者&#xff08;10.10.253.354&#xff09;&#xff0c;本案例按照3.18讲解。 1和1相连&#xff0c;0和电脑相连 本地电脑修改ip为192.168.3.3&#xff08;和3…...

Vue+element el-date-picker 时间日期选择器设置默认值,选择框不显示问题(已解决)

时间选择器默认值的问题 显示的时候如果用下面的方式赋值将不会显示出来&#xff1a; this.deviceFormData.time[0] that.$filterArray.formatDatehh(start);this.deviceFormData.time[1] that.$filterArray.formatDateEnd(end);实际上是有数据的&#xff0c;但是不会显示出…...

数据挖掘题目:根据规则模板和信息表找出R中的所有强关联规则,基于信息增益、利用判定树进行归纳分类,计算信息熵的代码

一、&#xff08;30分&#xff09;设最小支持度阈值为0.2500, 最小置信度为0.6500。对于下面的规则模板和信息表找出R中的所有强关联规则&#xff1a; S∈R&#xff0c;P&#xff08;S&#xff0c;x &#xff09;∧ Q&#xff08;S&#xff0c;y &#xff09;> Gpa&#xf…...

Reshape.XL 1.2 for Excel插件 Crack

特征 插件 Reshape.XL 包括 130 个基本可组合功能。使用它们&#xff0c;您可以快速轻松地进行非常复杂的数据转换和处理。它们的架构和基本定义受到 SQL 和 R 语言的强烈启发。 到目前为止&#xff0c;类似的功能只能通过脚本语言供程序员使用。借助 Reshape.XL 插件&#xf…...

开发知识点-PHP从小白到拍簧片

从小白到拍簧片 位异或运算&#xff08;^ &#xff09;引用符号(&)strlen() 函数base64_encode预定义 $_POST 变量session_start($array);操作符php 命令set_time_limit(7200)isset()PHP 命名空间(namespace)new 实例化类extends 继承 一个类使用另一个类方法error_reporti…...

飞书开发学习笔记(二)-云文档简单开发练习

飞书开发学习笔记(二)-云文档简单开发练习 一.云文档飞书开发环境API 首先还是进入开放平台 飞书开放平台&#xff1a;https://open.feishu.cn/app?langzh-CN 云文档相关API都在“云文档”目录中&#xff0c;之下又有"云空间",“文档”&#xff0c;“电子表格”&a…...

设计模式——命令模式(Command Pattern)+ Spring相关源码

文章目录 一、命令模式定义二、例子2.1 菜鸟教程例子2.1.1 定义命令类接口2.1.2 定义命令执行者2.1.3 被处理对象Stock。2.1.4 封装处理Stock的命令 2.2 JDK源码——Runnable2.2.1 命令接口2.2.2 命令处理者2.2.3 命令实现类 2.3 SpringMVC——Controller2.3.1 请求对象 handle…...

[开源]企业级在线办公系统,基于实时音视频完成在线视频会议功能

一、开源项目简介 企业级在线办公系统 本项目使用了SpringBootMybatisSpringMVC框架&#xff0c;技术功能点应用了WebSocket、Redis、Activiti7工作流引擎&#xff0c; 基于TRTC腾讯实时音视频完成在线视频会议功能。 二、开源协议 使用GPL-3.0开源协议 三、界面展示 部分…...

Scala语言用Selenium库写一个爬虫模版

首先&#xff0c;我将使用Scala编写一个使用Selenium库下载yuanfudao内容的下载器程序。 然后我们需要在项目的build.sbt文件中添加selenium的依赖项。以下是添加Selenium依赖项的代码&#xff1a; libraryDependencies "org.openqa.selenium" % "selenium-ja…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...