图论(蓝桥杯 C++ 题目 代码 注解)

目录

迪杰斯特拉模板(用来求一个点出发到其它点的最短距离):

克鲁斯卡尔模板(用来求最小生成树):

题目一(蓝桥王国):

题目二(随机数据下的最短路径): 

题目三(出差):

题目四(聪明的猴子):

 题目六(机房):

迪杰斯特拉模板(用来求一个点出发到其它点的最短距离):

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
const ll N = 3e5 + 10, M = 1e6 + 10, inf = 1e14;
struct  node
{ll v, w;bool operator <(const node& y) const//重载一个<,用于优先队列排序{return w > y.w;//小到大}
};
int n, m;
priority_queue<node>q;
vector<node> e[N];
ll dis[N], vis[N];
void Dij()
{dis[1] = 0;//从1号点出发,表示从1到1距离为0q.push({ 1,dis[1] });//1号点以及到1的距离入队while (q.size()){int u = q.top().v;//取最小边相连的点出队q.pop();if (vis[u])//访问过则跳过continue;vis[u] = 1;//没访问赋为访问for (auto i : e[u])//遍历以u为出发点的边{int v = i.v, w = i.w;//取其相连的点及权值if (dis[v] > dis[u] + w)//经过u点到v点的权值小于之前的权值则更新{dis[v] = dis[u] + w;q.push({ v,dis[v] });//v点以及到v的距离}}}}
int main()
{cin >> n >> m;fill(dis+1, dis+1+n, inf);//赋值一个无穷大,表示没有连接for (int i = 1; i <= m; i++){int x, y, w;cin >> x >> y >> w;e[x].push_back({ y,w });//存入以x出发到y,权值为w}Dij();
}

克鲁斯卡尔模板(用来求最小生成树):

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 1e3+20;
int m, n;
int h[N],f[N],x[N],y[N];
struct edge
{int v1, v2;double w;
};
vector<edge> e;
int find(int k)//查找
{if (f[k] == k)return k;return f[k] = find(f[k]);
}
void  merge(int x, int y)//合并
{x=find(x),y=find(y);if (x!= y)f[x] = f[y];
}
bool cmp(edge a, edge b)
{return a.w < b.w;
}
int main()
{cin >> n;for (int j = 1; j <= n; j++){cin >> x[j] >> y[j]>> h[j];f[j] = j;//初始化并查集根}cin>>m;for (int j = 1; j <= m; j++)//添加边{int v1,v2,w;cin>>v1>>v2>>w;e.push_back({ v1, v2, w });}sort(e.begin(), e.end(), cmp);//边从小到大排序int cnt=0;for (int i = 0; i < e.size(); i++){if (find(e[i].v1) != find(e[i].v2))//不属于一个集合{merge(e[i].v1, e[i].v2);//合并}if (cnt == n-1)//n个点只需要n-1条边,选取n-1条边后,跳出循环break;}
}

题目一(蓝桥王国):

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
const ll N = 3e5 + 10, M = 1e6 + 10, inf = 1e14;
struct  node
{ll v, w;bool operator <(const node& y) const//重载一个<,用于优先队列排序{return w > y.w;//小到大}
};
int n, m;
priority_queue<node>q;
vector<node> e[N];
ll dis[N], vis[N];
void Dij()
{dis[1] = 0;//从1号点出发,表示从1到1距离为0q.push({ 1,dis[1] });//1号点以及到1的距离入队while (q.size()){int u = q.top().v;//取最小边相连的点出队q.pop();if (vis[u])//访问过则跳过continue;vis[u] = 1;//没访问赋为访问for (auto i : e[u])//遍历以u为出发点的边{int v = i.v, w = i.w;//取其相连的点及权值if (dis[v] > dis[u] + w)//经过u点到v点的权值小于之前的权值则更新{dis[v] = dis[u] + w;q.push({ v,dis[v] });//v点以及到v的距离}}}}
int main()
{cin >> n >> m;fill(dis+1, dis+1+n, inf);//赋值一个无穷大,表示没有连接for (int i = 1; i <= m; i++){int x, y, w;cin >> x >> y >> w;e[x].push_back({ y,w });//存入以x出发到y,权值为w}Dij();for (int i = 1; i <= n; i++){if (dis[i] >= inf)//无法到达cout << -1 << " ";elsecout << dis[i] << " ";}
}

题目二(随机数据下的最短路径): 

 

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
const ll N = 3e5 + 10, M = 1e6 + 10, inf = 1e14;
struct  node
{ll v, w;bool operator <(const node& y) const//重载一个<,用于优先队列排序{return w > y.w;//小到大}
};
int n, m, t;
priority_queue<node>q;
vector<node> e[N];
ll dis[N], vis[N];
void Dij(int t)
{dis[t] = 0;//从t号点出发,表示从t到t距离为0q.push({ t,dis[t] });//t号点以及到t的距离入队while (q.size()){int u = q.top().v;//取最小边相连的点出队q.pop();if (vis[u])//访问过则跳过continue;vis[u] = 1;//没访问赋为访问for (auto i : e[u])//遍历以u为出发点的边{int v = i.v, w = i.w;//取其相连的点及权值if (dis[v] > dis[u] + w)//经过u点到v点的权值小于之前的权值则更新{dis[v] = dis[u] + w;q.push({ v,dis[v] });//v点以及到v的距离}}}}
int main()
{cin >> n >> m>> t;fill(dis+1, dis+1+n, inf);//赋值一个无穷大,表示没有连接for (int i = 1; i <= m; i++){int x, y, w;cin >> x >> y >> w;e[x].push_back({ y,w });//存入以x出发到y,权值为w}Dij(t);//从t点出发for (int i = 1; i <= n; i++){if (dis[i] == inf)//无法到达cout << -1 << " ";elsecout << dis[i] << " ";}
}

题目三(出差):

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
const ll N = 3e5 + 10, M = 1e6 + 10, inf = 1e14;
struct  node
{int v, w;bool operator <(const node& y) const//重载一个<,用于优先队列排序{return w > y.w;//小到大}
};
int n, m;
priority_queue<node>q;
vector<node> e[N];
int dis[N], vis[N], time0[N];
void Dij()
{dis[1] = 0;//从1号点出发,表示从1到1距离为0q.push({ 1,dis[1] });//1号点以及到1的距离入队while (q.size()){int u = q.top().v;//取最小边相连的点出队q.pop();if (vis[u])//访问过则跳过continue;vis[u] = 1;//没访问赋为访问for (auto i : e[u])//遍历以u为出发点的边{int v = i.v, w = i.w;//取其相连的点及权值if (dis[v] > dis[u] + w)//经过u点到v点的权值小于之前的权值则更新{dis[v] = dis[u] + w;q.push({ v,dis[v] });//v点以及到v的距离}}}
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++)cin >> time0[i];fill(dis + 1, dis + 1 + n, inf);//赋值一个无穷大,表示没有连接for (int i = 1; i <= m; i++){int x, y, w;cin >> x >> y >> w;e[x].push_back({ y,w + time0[y]});//存入以x出发到y,权值为w+隔离时间e[y].push_back({ x,w + time0[x] });//存入以y出发到y,权值为w+隔离时间}Dij();cout << dis[n] - time0[n];//要减掉最后终点的隔离时间
}

题目四(聪明的猴子):

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 1e3+20;
int m, n;
int a[N],f[N],x[N],y[N];
struct edge
{int v1, v2;double w;
};
vector<edge> e;
int find(int k)//查找
{if (f[k] == k)return k;return f[k] = find(f[k]);
}
void  merge(int x, int y)//合并
{x=find(x),y=find(y);if (x!= y)f[x] = f[y];
}
bool cmp(edge a, edge b)
{return a.w < b.w;
}
int main()
{cin >> m;for (int i = 1; i <= m; i++)cin >> a[i];cin >> n;for (int j = 1; j <= n; j++){cin >> x[j] >> y[j];f[j] = j;//初始化并查集根}for(int i=1;i<=n;i++)for (int j = i + 1; j <= n; j++)//添加边{double w = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));e.push_back({ i, j, w });}sort(e.begin(), e.end(), cmp);//边从小到大排序double maxw = 0.0;//记录最小生成树中最大边int cnt = 0;for (int i = 0; i < e.size(); i++){if (find(e[i].v1) != find(e[i].v2))//不属于一个集合{merge(e[i].v1, e[i].v2);//合并cnt++;maxw = max(maxw, e[i].w);//更新最小生成树中最大边}if (cnt == n-1)//n个点只需要n-1条边,选取n-1条边后,跳出循环break;}int ans = 0;for (int i = 1; i <= m; i++){if (a[i] >= maxw)//有几只猴子大于最小生成树中最大边ans++;}cout << ans;
}

题目五(通电):

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 1e3+20;
int m, n;
int h[N],f[N],x[N],y[N];
struct edge
{int v1, v2;double w;
};
vector<edge> e;
int find(int k)//查找
{if (f[k] == k)return k;return f[k] = find(f[k]);
}
void  merge(int x, int y)//合并
{x=find(x),y=find(y);if (x!= y)f[x] = f[y];
}
bool cmp(edge a, edge b)
{return a.w < b.w;
}
int main()
{cin >> n;for (int j = 1; j <= n; j++){cin >> x[j] >> y[j]>> h[j];f[j] = j;//初始化并查集根}for(int i=1;i<=n;i++)for (int j = i + 1; j <= n; j++)//添加边{double w = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]))+(h[i]-h[j])*(h[i]-h[j]);e.push_back({ i, j, w });}sort(e.begin(), e.end(), cmp);//边从小到大排序double maxw = 0.0;//记录最小生成树中最大边double ans=0;int cnt=0;for (int i = 0; i < e.size(); i++){if (find(e[i].v1) != find(e[i].v2))//不属于一个集合{merge(e[i].v1, e[i].v2);//合并ans+=e[i].w;//求和maxw = max(maxw, e[i].w);//更新最小生成树中最大边}if (cnt == n-1)//n个点只需要n-1条边,选取n-1条边后,跳出循环break;}printf("%.2lf",ans);
}

 题目六(机房):

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
const ll N = 3e5 + 10, M = 1e6 + 10;
struct  node
{ll v, w;bool operator <(const node& y) const//重载一个<,用于优先队列排序{return w > y.w;//小到大}
};
int n, m;
priority_queue<node>q;
vector<node> e[N];
vector<node> temp;
ll dis[N], vis[N], cnt[N];
ll Dij(int u, int end)
{memset(vis, 0, sizeof(vis));memset(dis, 0x3f3f, sizeof(dis));dis[u] = 0;//从u号点出发,表示从u到u距离为0q.push({ u,dis[u] });//u号点以及到u的距离入队while (q.size()){int u = q.top().v;//取最小边相连的点出队q.pop();if (vis[u])//访问过则跳过continue;vis[u] = 1;//没访问赋为访问for (auto i : e[u])//遍历以u为出发点的边{int v = i.v, w = i.w;//取其相连的点及权值if (dis[v] > dis[u] + w)//经过u点到v点的权值小于之前的权值则更新{dis[v] = dis[u] + w;q.push({ v,dis[v] });//v点以及到v的距离}}}return dis[end]+cnt[end];//还需要加上自身延迟
}
int main()
{cin >> n >> m;for (int i = 1; i <= n - 1; i++){int x, y;cin >> x >> y;cnt[x]++, cnt[y]++;temp.push_back({ x,y });//临时存两个顶点}for (int i = 0; i < n - 1; i++)//根据度构造边{int u = temp[i].v, v = temp[i].w;e[u].push_back({ v,cnt[u] });//u->v的边,权值为u的度e[v].push_back({ u,cnt[v] });}while (m--)//m次查询{int u, v;cin >> u >> v;if (u == v)cout << cnt[u] << endl;else{ll ans = Dij(u, v);cout << ans << endl;}}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/276960.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C++实验 面向对象编程

一、实验目的&#xff1a; 掌握类中静态成员的定义方法&#xff0c;初始化方法&#xff0c;使用方法&#xff1b; 掌握类的友元说明方法&#xff0c;理解友元的使用特点 二、实验内容&#xff1a; 1、编写程序&#xff0c;统计某旅馆住宿客人的总数&#xff0c;要求输入客人…

英国伦敦交易所股票清单列表数据API接口

# Restful API https://tsanghi.com/api/fin/stock/XLON/list?token{token}更新时间&#xff1a;收盘后3~4小时。 更新周期&#xff1a;每天。 请求方式&#xff1a;GET。 # 测试&#xff1a;返回不超过10条数据&#xff08;2年历史&#xff09; https://tsanghi.com/api/fin/…

Linux下的多线程编程:原理、工具及应用(2)

&#x1f3ac;慕斯主页&#xff1a;修仙—别有洞天 ♈️今日夜电波&#xff1a;Flower of Life—陽花 0:34━━━━━━️&#x1f49f;──────── 4:46 &#x1f504; ◀️ ⏸ ▶️ ☰ …

C++第五弹---类与对象(二)

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】【C详解】 类与对象 1、类对象模型 1.1、如何计算类对象的大小 1.2、类对象的存储方式猜测 1.3、结构体内存对齐规则 2、this指针 2.1、this指针的引出 2.2…

springboot275毕业就业信息管理系统的设计与实现

毕业就业信息管理系统设计与实现 摘 要 传统办法管理信息首先需要花费的时间比较多&#xff0c;其次数据出错率比较高&#xff0c;而且对错误的数据进行更改也比较困难&#xff0c;最后&#xff0c;检索数据费事费力。因此&#xff0c;在计算机上安装毕业就业信息管理系统软件…

【C语言进阶篇】数据在内存中的存储

目录 1.大小端字节序和字节序判断 2.浮点数在内存中的存储与读取 2.1 浮点数在内存中的存储 2.2 浮点数在内存中的读取 在前面的学习中&#xff0c;我们知道内存被划分为一个个小的内存单元&#xff0c;数据就是存储在这些内存单元中的。那么&#xff0c;具体是如何存储的&am…

Unity中的网格创建和曲线变形

Unity中的网格创建和曲线变形 3D贝塞尔曲线变形贝塞尔曲线基础线性公式二次方公式三次方公式 Unity 实现3D贝塞尔曲线变形准备工作脚本概述变量定义 变量解析函数解析 获取所有子节点GetAllChildren 获取所有子节点UpdateBezierBend 控制点更新CalculateBezier Bezier 曲线公式…

pytorch升级打怪(三)

数据集合数据加载器 简介加载数据集迭代和可视化数据集为您的文件创建自定义数据集__init____len____getitem__ 准备您的数据以使用DataLoaders进行训练通过DataLoader进行遍载 简介 处理数据样本的代码可能会变得混乱且难以维护&#xff1b;理想情况下&#xff0c;我们希望我…

三分钟快速理解Yarn的工作流程

知识讲解之前&#xff0c;我们先来听一段小故事(不要带入现实) 健鑫集团是一家公司&#xff0c;主要业务就是承接其他公司外包出去的项目&#xff0c;这地方是怎么运行的呢&#xff1f; 外部想和集团达成合作&#xff0c;草拟个合同直接和 Boss谈&#xff0c;Boss 来者不拒&am…

智慧城市:提升城市治理能力的关键

目录 一、智慧城市的概念及特点 二、智慧城市在提升城市治理能力中的应用实践 1、智慧交通&#xff1a;提高交通治理效率 2、智慧政务&#xff1a;提升政府服务水平 3、智慧环保&#xff1a;加强环境监测与治理 4、智慧安防&#xff1a;提高城市安全水平 三、智慧城市在…

css 各种方位计算 - client系列 offset系列 scroll系列 x/y 系列

offset系列 HTMLElement.offsetTop - Web API 接口参考 | MDN 一文读懂offsetHeight/offsetLeft/offsetTop/offsetWidth/offsetParent_heightoffset-CSDN博客 client系列 搞清clientHeight、offsetHeight、scrollHeight、offsetTop、scrollTop-CSDN博客 scroll系列 秒懂scr…

Python控制摄像头并获取数据文件

一、引言 摄像头作为计算机视觉领域的核心设备之一&#xff0c;广泛应用于视频监控、图像采集和数据处理等领域。通过Python编程语言&#xff0c;我们可以实现对摄像头的精确控制&#xff0c;包括摄像头的开启、关闭、参数设置以及数据获取等功能。 目录 一、引言 二、摄像头…

ElementUI Message 消息提示,多个显示被覆盖的问题

现象截图&#xff1a; 代码&#xff1a;主要是在this.$message 方法外层加上 setTimeout 方法 <script> export default {name: "HelloWorld",props: {msg: String,},methods: {showMessage() {for (let i 0; i < 10; i) {setTimeout(() > {this.$mess…

上海亚商投顾:沪指震荡调整 飞行汽车概念股持续爆发

上海亚商投顾前言&#xff1a;无惧大盘涨跌&#xff0c;解密龙虎榜资金&#xff0c;跟踪一线游资和机构资金动向&#xff0c;识别短期热点和强势个股。 一.市场情绪 沪指昨日震荡调整&#xff0c;深成指走势稍强&#xff0c;创业板指一度涨超1%&#xff0c;黄白二线走势分化&a…

鸿蒙Harmony应用开发—ArkTS声明式开发(容器组件:ColumnSplit)

将子组件纵向布局&#xff0c;并在每个子组件之间插入一根横向的分割线。 说明&#xff1a; 该组件从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 子组件 可以包含子组件。 ColumnSplit通过分割线限制子组件的高度。初始…

微信小程序--开启下拉刷新页面

1、下拉刷新获取数据enablePullDownRefresh 开启下拉刷新&#xff1a; enablePullDownRefreshbooleanfalse是否开启当前页面下拉刷新 案例&#xff1a; 下拉刷新&#xff0c;获取新的列表数据,其实就是进行一次新的网络请求&#xff1a; 第一步&#xff1a;在.json文件中开…

【论文阅读】ACM MM 2023 PatchBackdoor:不修改模型的深度神经网络后门攻击

文章目录 一.论文信息二.论文内容1.摘要2.引言3.作者贡献4.主要图表5.结论 一.论文信息 论文题目&#xff1a; PatchBackdoor: Backdoor Attack against Deep Neural Networks without Model Modification&#xff08;PatchBackdoor:不修改模型的深度神经网络后门攻击&#xf…

DDR协议基础进阶(三)——(基本功能、初始化、MR寄存器)

DDR协议基础进阶&#xff08;三&#xff09;——&#xff08;基本功能、初始化、MR寄存器&#xff09; 一、DDR基本功能 DDR基本功能主要包括&#xff1a; 8-bit prefetch预取——8-bit&#xff0c;是指8位数据&#xff0c;即8倍芯片位宽的数据。由于DDR内部数据传输是32bit…

大型政企迈向数智化深水区,如何保障安全用云?

文&#xff5c;白 鸽 编&#xff5c;王一粟 在这个千行万业加速智能升级的时代&#xff0c;我们应该如何保证数字安全&#xff1f; 一方面&#xff0c;AI技术快速发展给当下带来一系列新型挑战&#xff1a;自动化攻击、深度伪造、隐私侵犯、数据安全等等。另一方面&#…

群晖NAS使用Docker安装WPS Office并结合内网穿透实现公网远程办公

文章目录 推荐1. 拉取WPS Office镜像2. 运行WPS Office镜像容器3. 本地访问WPS Office4. 群晖安装Cpolar5. 配置WPS Office远程地址6. 远程访问WPS Office小结 7. 固定公网地址 推荐 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff…