图论（蓝桥杯 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距离为0
    q.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;//初始化并查集根
    }
    for(int i=1;i<=n;i++)
        for (int j = i + 1; j <= n; j++)//添加边
        {
            int w;
            cin>>w;
            e.push_back({ i, j, 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距离为0
    q.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 << " ";
        else
            cout << 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距离为0
    q.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 << " ";
        else
            cout << 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距离为0
	q.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距离为0
    q.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;
        }
    }
}

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

基于EasyCVR视频技术的流媒体视频融合与汇聚管理系统建设方案

基于EasyCVR视频技术的流媒体视频融合与汇聚管理系统建设方案

流媒体视频融合与汇聚管理系统可以实现对各类模块化服务进行统一管理和配置等操作&#xff0c;可实现对应用服务的整合、管理及共享&#xff0c;以标准接口的方式&#xff0c;业务平台及其他第三方业务平台可以方便地调用各类数据&#xff0c;具有开放性和可扩展性。在流媒体视…
阅读更多...
前后端链条产生的跨域问题

前后端链条产生的跨域问题

环境&#xff1a; vitevue3 .net 6 vsstudio2022C# asp .net core webapi 看别的up说这个第一条报错是因为&#xff1a;后端没有允许跨域导致的 解决办法: 1.在后端添加允许跨域 Program.cs //添加跨域策略builder.Services.AddCors(options >{options.AddPolicy(…
阅读更多...
生成式人工智能服务安全基本要求实务解析

生成式人工智能服务安全基本要求实务解析

本文尝试明晰《基本要求》的出台背景与实践定位&#xff0c;梳理《基本要求》所涉的各类安全要求&#xff0c;以便为相关企业遵循执行《基本要求》提供抓手。 引言 自2022年初以来&#xff0c;我国陆续发布算法推荐、深度合成与生成式人工智能服务相关的规范文件&#xff0c;…
阅读更多...
ARM学习（25）链接装载高阶认识

ARM学习（25）链接装载高阶认识

ARM学习&#xff08;25&#xff09;链接装载高阶认识 1、例子引出 笔者先引入几个编译链接的例子来介绍一下&#xff1a; 声明无效&#xff1a;declared implicitly&#xff1f;&#xff0c;属于编译错误还是链接错误&#xff1f; 编译阶段的错误&#xff0c;属于编译错误&am…
阅读更多...
【C++教程从0到1入门编程】第八篇:STL中string类的模拟实现

【C++教程从0到1入门编程】第八篇:STL中string类的模拟实现

一、 string类的模拟实现 下面是一个列子 #include <iostream> namespace y {class string{public: //string() //无参构造函数// :_str(nullptr)//{}//string(char* str) //有参构造函数// :_str(str)//{}string():_str(new char[1]){_str[0] \0;}string(c…
阅读更多...
【数据分享】2008-2022年全国范围逐年NO2栅格数据（免费获取）

【数据分享】2008-2022年全国范围逐年NO2栅格数据（免费获取）

空气质量数据是在我们日常研究中经常使用的数据&#xff01;之前我们给大家分享了2000-2022年全国范围逐年的PM2.5栅格数据、2013-2022年全国范围逐年SO2栅格数据、2013-2022年全国范围逐年CO栅格数据和2000-2022年全国范围逐年PM10栅格数据&#xff08;可查看之前的文章获悉详…
阅读更多...
力扣--深度优先算法/回溯算法47.全排列 Ⅱ

力扣--深度优先算法/回溯算法47.全排列 Ⅱ

思路分析&#xff1a; 使用DFS算法进行全排列&#xff0c;递归地尝试每个可能的排列方式。使用 path 向量保存当前正在生成的排列&#xff0c;当其大小达到输入数组的大小时&#xff0c;将其加入结果集。使用 numvisited 向量标记每个数字是否已经被访问过&#xff0c;以确保每…
阅读更多...
科技助力床垫升级，康姿百德实体店品质有保障

科技助力床垫升级，康姿百德实体店品质有保障

在现代社会的快节奏生活中&#xff0c;高质量的睡眠已成为许多人追求的目标。睡眠质量不仅影响着我们的日常生活和工作效率&#xff0c;而且直接关系到身体健康。康姿百德床垫&#xff0c;作为市场上的优选产品&#xff0c;致力于为消费者提供舒适、健康的睡眠体验&#xff0c;…
阅读更多...
ArcGIS学习（十七）基于GIS平台的水文分析

ArcGIS学习（十七）基于GIS平台的水文分析

ArcGIS学习（十七）基于GIS平台的水文分析 本任务我们来学习”如何结合ArcGIS做水文分析？” 首先要说明的是，这个任务的水文分析是以ArcGIS工具视角来讲的。而水文分析也是“水文学”这个更大的概念下的一个分析方法。 水文学中研究最多的是水文循环，水文循环是一个物理过程…
阅读更多...
Ansible介绍以及功能

Ansible介绍以及功能

ansible功能 批量执行远程命令,可以对远程的多台主机同时进行命令的执行 批量安装和配置软件服务&#xff0c;可以对远程的多台主机进行自动化的方式配置和管理各种服务 编排高级的企业级复杂的IT架构任务, Ansible的Playbook和role可以轻松实现大型的IT复杂架构 提供自动化…
阅读更多...
鸿蒙Harmony应用开发—ArkTS声明式开发（基础手势：Stepper）

鸿蒙Harmony应用开发—ArkTS声明式开发（基础手势：Stepper）

步骤导航器组件&#xff0c;适用于引导用户按照步骤完成任务的导航场景。 说明&#xff1a; 该组件从API Version 8开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 子组件 仅能包含子组件StepperItem。 接口 Stepper(value?: { index?…
阅读更多...
基于ARMA-GARCH模型探究股价的日历效应和节假日效应【思路+代码】

基于ARMA-GARCH模型探究股价的日历效应和节假日效应【思路+代码】

目录 1. 模型定义1.1 ARMA-GARCH模型1.2 引入节假日效应的虚拟变量的新模型1.3 引入日历效应的虚拟变量的新模型 2. 实证部分2.1 准备工作2.2 引入节假日效应虚拟变量的模型建立和结果分析2.3 引入节假日效应和日历效应的虚拟变量的模型建立和结果分析 3. 结语 本文介绍了ARMA-…
阅读更多...
5.Java并发编程—JUC线程池架构

5.Java并发编程—JUC线程池架构

JUC线程池架构 在Java开发中&#xff0c;线程的创建和销毁对系统性能有一定的开销&#xff0c;需要JVM和操作系统的配合完成大量的工作。 JVM对线程的创建和销毁&#xff1a; 线程的创建需要JVM分配内存、初始化线程栈和线程上下文等资源&#xff0c;这些操作会带来一定的时间和…
阅读更多...
YOLOv9改进 添加新型卷积注意力框架SegNext_Attention

YOLOv9改进 添加新型卷积注意力框架SegNext_Attention

一、SegNext论文 论文地址：2209.08575.pdf (arxiv.org) 二、 SegNext_Attention注意力框架结构 在SegNext_Attention中，注意力机制被引入到编码器和解码器之间的连接中，帮助模型更好地利用全局上下文信息。具体而言，注意力机制通过学习像素级的注意力权重，使得模型可以对…
阅读更多...
基于log4cpp封装日志类

基于log4cpp封装日志类

一、log4cpp的使用 1. 下载log4cpp log4cpp官方下载地址 2. 安装log4cpp 第一步&#xff1a;解压 tar zxvf log4cpp-1.1.4.tar.gz 第二步&#xff1a;进入log4cpp文件夹并执行 ./configure tips&#xff1a;如果是ARM架构的CPU可能会失败&#xff0c;如下面这种情况&a…
阅读更多...
力扣热题100_矩阵_54_螺旋矩阵

力扣热题100_矩阵_54_螺旋矩阵

文章目录 题目链接解题思路解题代码 题目链接 54. 螺旋矩阵 给你一个 m 行 n 列的矩阵 matrix &#xff0c;请按照 顺时针螺旋顺序 &#xff0c;返回矩阵中的所有元素。 示例 1&#xff1a; 输入&#xff1a;matrix [[1,2,3],[4,5,6],[7,8,9]] 输出&#xff1a;[1,2,3,6,9…
阅读更多...
图片和PDF 加水印去水印

图片和PDF 加水印去水印

图片和PDF 加水印去水印 前要1. 图片加水印1.1 方法11.2 方法2 2. 去水印3. pdf加水印4. pdf 去水印 前要 网上查了很多资料, 汇总了几个不错的代码, 顺便做个笔记 1. 图片加水印 1.1 方法1 简单方便, 后也好处理 # -*- coding:utf-8 -*- import os from PIL import Imag…
阅读更多...
第四弹：Flutter图形渲染性能

第四弹：Flutter图形渲染性能

目标&#xff1a; 1&#xff09;Flutter图形渲染性能能够媲美原生&#xff1f; 2&#xff09;Flutter性能优于React Native? 一、Flutter图形渲染原理 1.1 Flutter图形渲染原理 Flutter直接调用Skia 1&#xff09;Flutter将一帧录制成SkPicture&#xff08;skp&#xff…
阅读更多...
吴恩达 x Open AI ChatGPT ——如何写出好的提示词视频核心笔记

吴恩达 x Open AI ChatGPT ——如何写出好的提示词视频核心笔记

核心知识点脑图如下&#xff1a; 1、第一讲&#xff1a;课程介绍 要点1&#xff1a; 上图展示了两种大型语言模型&#xff08;LLMs&#xff09;的对比&#xff1a;基础语言模型&#xff08;Base LLM&#xff09;和指令调整语言模型&#xff08;Instruction Tuned LLM&#xff0…
阅读更多...
ARM64汇编06 - 基本整型运算指令

ARM64汇编06 - 基本整型运算指令

ADD (immediate) 将 Xn 与 imm 相加&#xff0c;结果赋值给 Xd&#xff0c;imm 是无符号数&#xff0c;范围为 0 - 4095。 shift 是对 imm 进行移位&#xff0c;shift 为 0 的时候&#xff0c;表示左移 0 位&#xff0c;即不变。shift 为 1 的时候&#xff0c;表示左移12 位&a…
阅读更多...
最新文章

Copyright @ 2022~2023