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

图论(蓝桥杯 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;}}
}

相关文章:

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

目录 迪杰斯特拉模板&#xff08;用来求一个点出发到其它点的最短距离&#xff09;&#xff1a; 克鲁斯卡尔模板&#xff08;用来求最小生成树&#xff09;&#xff1a; 题目一&#xff08;蓝桥王国&#xff09;&#xff1a; 题目二&#xff08;随机数据下的最短路径&#…...

矩阵起源新一年喜报连连!

新春伊始 矩阵起源向大家分享 一连串好消息 首先&#xff0c;公司创始人兼CEO王龙先生获评“2023深圳创新突出贡献人物“。这一荣誉是对其在推动数据库行业技术创新和产品开发方面所做出的卓越贡献的认可。他的领导力和创新精神不仅引领我司取得了显著的成就&#xff0c;也为…...

牛客——紫魔法师(并查集)

链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源&#xff1a;牛客网 题目描述 “サーヴァント、キャスター、Medea。”--紫魔法师 给出一棵仙人掌(每条边最多被包含于一个环&#xff0c;无自环&#xff0c;无重边&#xff0c;保证连通)&#xff0c;要求用最少的…...

最新WooCommerce教程指南-如何搭建B2C外贸独立站

WooCommerce是全球最受欢迎的开源电子商务平台之一。它基于WordPress建站&#xff0c;只需一键安装即可使用。该平台提供了丰富的功能&#xff0c;包括产品发布、库存管理、支付网关和运输发货等&#xff0c;可以帮助搭建各种类型的电子商务网站。相比其他竞争对手&#xff0c;…...

一文教会你SpringBoot是如何启动的

SpringBoot启动流程分析 流程图 源码剖析 运行Application.run()方法 我们在创建好一个 SpringBoot 程序之后&#xff0c;肯定会包含一个类&#xff1a;xxxApplication&#xff0c;我们也是通过这个类来启动我们的程序的&#xff08;梦开始的地方&#xff09;&#xff0c;而…...

车载测试面试:各大车企面试题汇总

本博主可协助大家成功进军车载测试行业 TBOX 深圳 涉及过T-BOX测试吗Ota升级涉及的台架环境是什么样的&#xff1f;上车实测之前有没有一个仿真环境台架环境都什么零部件T-BOX了解多少Linux和shell有接触吗 单片机uds诊断是在实车上座的吗 uds在实车上插的那口 诊断仪器是哪…...

Qt散文一

Qt的事件分为普通事件和系统事件&#xff0c;普通事件比如用户按下键盘&#xff0c;系统事件比如定时器事件。事件循环的开始是从main函数的QApplication&#xff0c;然后调用exec()开始的&#xff0c;在执行exec()函数之后&#xff0c;程序将进入事件循环来监听应用程序的事件…...

MySQL学习Day32——数据库备份与恢复

在任何数据库环境中&#xff0c;总会有不确定的意外情况发生&#xff0c;比如例外的停电、计算机系统中的各种软硬件故障、人为破坏、管理员误操作等是不可避免的&#xff0c;这些情况可能会导致数据的丢失、 服务器瘫痪等严重的后果。存在多个服务器时&#xff0c;会出现主从服…...

阅读基础知识

一 网络 1. 三次握手四次挥手 三次握手&#xff1a;为了建立长链接进行交互即建立一个会话&#xff0c;使用 http/https 协议 ① 客户端产生初始化序列号 Seqx &#xff0c;向服务端发送建立连接的请求报文&#xff0c;将 SYN1 同步序列号&#xff1b; ② 服务端接收建立连接…...

【NestJS 编程艺术】1. NestJS设计模式深度解析:构建高效、可维护的服务端应用

在当今快速发展的软件开发领域&#xff0c;Node.js凭借其轻量级和高性能的特点&#xff0c;已经成为了构建服务端应用的首选技术之一。然而&#xff0c;随着应用规模的扩大&#xff0c;传统的Node.js框架如Express和Koa可能在架构设计和代码组织上显得力不从心。这时&#xff0…...

QT中connect()的参数5:Qt::DirectConnection、Qt::QueuedConnection区别

原文链接&#xff1a;https://blog.csdn.net/Dasis/article/details/120916993 connect用于连接QT的信号和槽&#xff0c;在qt编程过程中不可或缺。它其实有第5个参数&#xff0c;只是一般使用默认值&#xff0c;在满足某些特殊需求的时候可能需要手动设置。 Qt::AutoConnect…...

VXLAN学习笔记

声明&#xff1a;该博客内容大部分参考参考链接整理 什么是VXLAN&#xff1f; VXLAN(Virtual Extensible LAN)即虚拟扩展局域网&#xff0c;是大二层网络中广泛使用的网络虚拟化技术。在源网络设备与目的网络设备之间建立一条逻辑VXLAN隧道&#xff0c;采用MAC in UDP的封装方…...

全排列的不同写法(茴字的不同写法)及对应的时间开销

资源课件&#xff1a; CS106B-recursion-pptstanford library-timer.hstanford library-set.h 不同的方法 1------ Set<string> permutations1Rec(string remaining) {Set<string> res;if(remaining.size() 0) {res "";}else {for(int i 0; i <…...

权衡后台数据库设计中是否使用外键

目录 引言 外键简介 对比 真实后台项目中的权衡 结论 引言 在大学学习数据库课程时&#xff0c;我们会早早的接触到外键这一概念&#xff0c;同时我相信大部分人在懂了外键的概念后都会觉得外键很重要&#xff0c;在涉及多表一定要用&#xff0c;但后来在我接触到真实项目…...

ChatGPT提示词方法的原理

关于提示词&#xff0c;我之前的一些文章可以参考&#xff1a; 【AIGC】AI作图最全提示词prompt集合&#xff08;收藏级&#xff09;https://giszz.blog.csdn.net/article/details/134815245?ydrefereraHR0cHM6Ly9tcC5jc2RuLm5ldC9tcF9ibG9nL21hbmFnZS9hcnRpY2xlP3NwbT0xMDExL…...

计算机网络 谢希仁(001-1)

计算机网络-方老师 总时长 24:45:00 共50个视频&#xff0c;6个模块 此文章包含1.1到1.4的内容 简介 1.1计算机网络的作用 三网融合&#xff08;三网合一&#xff09; 模拟信号就是连续信号 数字信号是离散信号 1.2互联网概述 以前2兆带宽就要98 现在几百兆带宽也就几百块 …...

Windows,MacOS,Linux下载python并配置环境图文讲解

Windows 打开python官网 点击download 点击黄色按钮 另存为 打开文件 全选 配置安装路径 安装中 关闭路径长度限制 完成 验证 同时按住winr(win就是空格键左边的东西) 输入cmd 键入python,如果出现版本(红框)即安装成功 MacOS 同理打开python官网 点击最新版本 拖…...

汽车网络基础知识 要点

在以太网开发中&#xff0c;常常会听到一些专业名词&#xff0c;例如PHY&#xff0c;MAC&#xff0c;MII&#xff0c;switch&#xff0c;下面是解释 PHY PHY 是物理接口收发器&#xff0c;它实现物理层。包括 MII/GMII (介质独立接口) 子层、PCS (物理编码子层) 、PMA (物理介…...

ClickHouse中的设置的分类

ClickHouse中的各种设置 ClickHouse中的设置有几百个&#xff0c;下面对这些设置做了一个简单的分类。...

香港空间服务器带宽和流量限制:原因和解决方法

​  香港空间服务器&#xff0c;也被称作香港虚拟服务器。一般情况下&#xff0c;香港空间服务器所提供的流量或者带宽&#xff0c;是足以满足99%的普通中小网站用户使用的&#xff0c;但也不排除&#xff0c;网站访问量大&#xff0c;租香港空间不能够满足要求的情况。 在本…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...