算法提高-图论-单源最短路的综合应用

单源最短路的综合应用

  • 单源最短路的综合应用
    • AcWing 1135. 新年好
    • AcWing 340. 通信线路
    • AcWing 342. 道路与航线
    • AcWing 341. 最优贸易

单源最短路的综合应用

AcWing 1135. 新年好

多次dijkstra求每个点到其它点的最短距离， 此时相当于建好了一张图，每个点之间的最短距离都知道了，接下来dfs搜一下怎么走最短即可

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second

const int N = 5 * 1e4 + 10, M = 2 * 1e5 + 10, INF = 0x3f3f3f3f;

int dist[6][N];
int e[M], ne[M], w[M], h[N], idx;
int source[6];
bool st[N];
 int n, m;

void add (int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ; 
}




void dijkstra(int start, int dist[])
{
    memset(st, 0, sizeof st);//求多次dijkstra，st每次都要初始化
    memset(dist, 0x3f, N * sizeof (int));
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    
    dist[start] = 0;//这里的dist是局部的，只不过重名了罢了，所以是一维的
        
    heap.push({dist[start], start});//PII根据第一个排序，所以dist放最前面,堆优化版dijksra就是存PII<dist, index>的
    
    while (heap.size())
    {
        PII t = heap.top();
        heap.pop();
        int ver = t.y;
        
        if(st[ver]) continue;
        st[ver] = true;
        
        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}


int dfs(int u, int start, int distance)
{
    if (u == 6) return distance;//最多6层（佳佳自己的家 + 5个亲戚），为什么不是7，因为到佳佳自己的家距离为0，我们不需要计算，只需要计算5层就行，不需要真正计算6层
    
    int res = INF;
    
    for (int i = 1; i <= 5; i ++ )//遍历next是哪个站，每个i对应一个source[i]是有实际意义的
    {
        if(!st[i])
        {
            int next = source[i];
            st[i] = true;
            res = min(res, dfs(u + 1, i, distance + dist[start][next]));//start传i的原因是到了下一层之后起点就是source[i]了，只不过在本层它是next而已
            st[i] = false;//要回溯
        }
    }
    
    return res;
}


int main()
{
    memset(h, -1, sizeof h);
    
   
    cin >> n >> m;
    source[0] = 1;
    for (int i = 1; i <= 5; i ++ ) cin >> source[i];

    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    
    for (int i = 0; i < 6; i ++ ) dijkstra(source[i], dist[i]);
    
    memset(st, 0, sizeof st);//dijkstra和dfs共用一个st数组，因此做完dij后要重置st数组给dfs遍历用
    
    cout << dfs(1, 0, 0);//1指的是第一层，0指的是start是source[0]也就是车站1（佳佳的家），0指的是当前距离为0
    return 0;
}

AcWing 340. 通信线路

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1e3 + 10, M = 2 * 1e4 + 10;

int n, m, k;
bool st[N];
int dist[N];
deque<int> q;
int e[M], h[N], w[M], ne[M], idx;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool check(int bound)
{
    memset(st, 0, sizeof st);//因为进行多从check，所以要重置
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    q.push_back(1);
    
    while (q.size())
    {
        int t = q.front();
        q.pop_front();
        
        if (st[t]) continue;
        st[t] = true;
        
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i], v = w[i] > bound;//如果大于，改边的边权就是1，代表当前大于mid的边增加1
            if (dist[j] > dist[t] + v)
            {
                dist[j] = dist[t] + v;
                if (v == 0) q.push_front(j);
                else q.push_back(j);
            }
        }
    }
    return dist[n] <= k;//判断到n点的路径大于mid的边是否<=k
}

int main()
{
    cin >> n >> m >> k;
    
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    
    int l = 0, r = 1e6 + 1;//为什么不是1-1e6,l取0是因为答案可能取0，比如3条边 k =3,那么答案就不用付钱。 
                           //答案可能取1e6，假如第k+1条边正好是1e6，但是题目有不连通的情况，因此取1e6+1，判断是否联通
    
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    
    if (r == 1e6 + 1) cout << "-1";
    else cout << r;
    return 0;
}

AcWing 342. 道路与航线

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second

const int N = 25000 + 10, M = 3 * 5 * 1e4 + 10, INF = 0x3f3f3f3f;

int h[N], e[M], w[M], ne[M], idx;

int id[N], din[N];
vector<int> block[N];

bool st[N];
int dist[N];
queue<int> q;//存储团

int n, mR, mP, S;
int bcnt;

void add (int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int bid)
{
    id[u] = bid, block[bid].push_back(u);//记录每个团内有哪些点，有多个团，因此vector是二维的
    
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (id[j] == 0) dfs(j, bid);
    }
}


void dijkstra(int bid)
{
    //虽然多次进行dijkstra，但是每次dij遍历的点的下标都是不同的，因此st数组不用重置
    priority_queue<PII, vector<PII>, greater<PII>> heap;//每个团都用一个堆去存这个团内的点
    
    for (auto u : block[bid])
        heap.push({dist[u], u});
    
    while (heap.size())
    {
        PII t = heap.top();
        heap.pop();
        int distance = t.x, ver = t.y; 
        if (st[ver]) continue;
        st[ver] = true;
        
        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (id[ver] != id[j] && -- din[id[j]] == 0) q.push(id[j]);//如果两点不在一个团内，将那个点的入度减1，如果为0，则加入拓扑序列中
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                if (id[ver] == id[j]) heap.push({dist[j], j});//如果这两个点在一个团内，再将j点加入当前团的堆
            }
        }
    }
}


//为什么按拓扑序会得到最少花费，因为每次入队也就是允许访问的节点的入度为0，
//这保证我们到此点的所有路径已经被走过并且在此过程中不断更新最短距离，
//当我们开始访问入度为0的点时，已经没有其他到此点的路径去更新它的最短距离

//（没太懂下面这句话啥意思）
//这道题没有存团之间的最短距离，也没什么意义，
//而是当dij遍历到有向边时更新访问到的另一个团中点的最短距离，
//实际上与上面的类似，也可以保证当访问每个入度为0的点时，
//团类的所有点没有其他没有访问过的从其他团到此点的路径
void topsort()
{
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;
    
    for (int i = 1; i <= bcnt; i ++ )
    {
        if (din[i] == 0) q.push(i);//入度为0的团就加入拓扑序列中
    }
    
    while (q.size())//遍历每个团
    {
        int t = q.front();
        q.pop();
        
        dijkstra(t);//dij每个团的同时更新拓扑序列 if (id[ver] != id[j] && -- din[id[j]] == 0) q.push(id[j]);
    }
}

int main ()
{
    cin >> n >> mR >> mP >> S;
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < mR; i ++ )
    {
        int a , b, c;
        cin >> a >> b >> c;
        add (a, b, c), add (b, a, c);
    }
    
    
    for (int i = 1; i <= n; i ++ )//初始化各个团以及各个团有哪些点
    {
        if (id[i] == 0)
        {
            id[i] = ++ bcnt;
            dfs(i, bcnt);
        }
    }
    
    for (int i = 0; i < mP; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add (a, b, c);
        din[id[b]] ++;//P是航线，连接各个团，b是单向边的目的地，因此b所在的团入度+1
    }
    
    topsort();
    
    for (int i = 1; i <= n; i ++ )
    {
        if (dist[i] > INF / 2) cout << "NO PATH" << endl;//因为有负边，所以只要判断结果大于一个比较大的数就说明不连通
        else cout << dist[i] << endl;
    }
    return 0;
}

AcWing 341. 最优贸易

一篇博客解释了为什么一个正向建图求最小值，反向建图求最大值
根本思想是保证1到n的买卖是连通的
在这里插入图片描述

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, M = 2 * 2 * 5 * 1e5 + 10;//题目给的有的是双向边有的是单向边，同时我们需要建两个图再乘2

int q[N], dmin[N], dmax[N];
int n, m;
int w[N];//存储的是每个城市的水晶球价格，而不是边权，所以开N的大小
int rh[N], h[N], e[M], ne[M], idx;
bool st[N];


void add(int h[], int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void spfa(int h[], int dist[], int type)
{
    int hh = 0, tt = 1;
    
    if (type == 0)
    {
        memset(dist, 0x3f, sizeof dmin);//或者sizeof int
        dist[1] = w[1];
        q[0] = 1;
    }
    else
    {
        memset(dist, -0x3f, sizeof dmax);
        dist[n] = w[n];
        q[0] = n;
    }
    
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;
        
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (type == 0 && dist[j] > min(dist[t], w[j]) || type == 1 && dist[j] < max(dist[t], w[j]))
            {
                if (type == 0) dist[j] = min(dist[t], w[j]);
                else dist[j] = max(dist[t], w[j]);
                
                if (st[j] == 0)
                {
                    q[tt ++] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    
}


int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> w[i];
    
    memset(h, -1, sizeof h), memset(rh, -1, sizeof rh);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, type;
        cin >> a >> b >> type;
        add(h, a, b), add(rh, b, a);
        if (type == 2)
            add(h, b, a), add(rh, a, b);
    }
    
    spfa(h, dmin, 0);
    spfa(rh, dmax, 1);
    
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        res = max(res, (dmax[i] - dmin[i]));//正向图遍历从1到i可以买入水晶球的最小值，反向图遍历从n到i可以卖出水晶求的最大值，两者求差
    cout << res;
    return 0;
}

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

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

相关文章

实验篇(7.2) 09. 通过安全隧道走对方宽带上网 (FortiClient-IPsec) ❀ 远程访问

实验篇(7.2) 09. 通过安全隧道走对方宽带上网 (FortiClient-IPsec) ❀ 远程访问

【简介】要想所有的流量都走安全隧道&#xff0c;就需要禁用隧道分割。这样上网流量也会通过隧道到达远端防火墙&#xff0c;再通过远端防火墙的宽带接口去到互联网。我们来看看FortiClient客户端用IPsec VPN是如何实现的。 实验要求与环境 OldMei集团深圳总部防火墙有两条宽带…
阅读更多...
【运筹优化】最短路算法之A星算法 + Java代码实现

【运筹优化】最短路算法之A星算法 + Java代码实现

文章目录 一、A星算法简介二、A星算法思想三、A星算法 java代码四、测试 一、A星算法简介 A*算法是一种静态路网中求解最短路径最有效的直接搜索方法&#xff0c;也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近&#xff0c;最终搜索速度越快。 二、A星算…
阅读更多...
javaScript蓝桥杯-----天气趋势 A

javaScript蓝桥杯-----天气趋势 A

目录 一、介绍二、准备三、目标四、代码五、完成 一、介绍 日常生活中&#xff0c;气象数据对于人们的生活具有非常重要的意义&#xff0c;数据的表现形式多种多样&#xff0c;使用图表进行展示使数据在呈现上更加直观。 本题请实现一个 Y 城 2022 年的天气趋势图。 二、准备…
阅读更多...
100天精通Python（可视化篇）——第88天：全网最全Seaborn库常用绘图3万字总结（参数说明+案例实战）

100天精通Python（可视化篇）——第88天：全网最全Seaborn库常用绘图3万字总结（参数说明+案例实战）

文章目录 一、Seaborn介绍1.1 介绍1.2 安装1.3 风格设置1.3.1 style&#xff08;风格&#xff09;1.3.2 context&#xff08;环境设置&#xff09; 1.4 调色盘设置1.5 数据集下载 二、Relational plots&#xff08;关系图&#xff09;2.1 scatterplot&#xff08;散点图&#x…
阅读更多...
SpringSecurity 总结

SpringSecurity 总结

SpringSecurity 总结 第一章 权限管理 权限管理SpringSecurity 简介整体架构 权限管理&#xff1a; 实现: "对用户访问系统的控制"(身份认证) &#xff0c; 按照 "安全规则"或者 "安全策略" (对已经认证的用户进行授权) 控制&#xff0c;用…
阅读更多...
K8s in Action 阅读笔记——【13】Securing cluster nodes and the network

K8s in Action 阅读笔记——【13】Securing cluster nodes and the network

K8s in Action 阅读笔记——【13】Securing cluster nodes and the network 13.1 Using the host node’s namespaces in a pod Pod中的容器通常在不同的Linux名称空间下运行&#xff0c;这使得它们的进程与其他容器或节点默认名称空间下运行的进程隔离开来。 例如&#xff…
阅读更多...
【计算机组成与体系结构Ⅰ】课程设计——基于Logisim的模型计算机设计

【计算机组成与体系结构Ⅰ】课程设计——基于Logisim的模型计算机设计

基于Logisim的模型计算机设计 一、实验目的 基于Logisim软件&#xff0c;根据一个模型指令系统&#xff0c;在逐步学习和了解计算机组成各部分逻辑组成和各部分互联的基础上&#xff0c;深入理解课程中的知识点&#xff0c;利用此软件设计并实现一个模拟的8位模型计算机原型。…
阅读更多...
Python爬取影评并进行情感分析和数据可视化

Python爬取影评并进行情感分析和数据可视化

Python爬取影评并进行情感分析和数据可视化 文章目录 Python爬取影评并进行情感分析和数据可视化一、引言二、使用requestsBeautifulSoup进行影评的爬取1、分析界面元素2、编写代码 三、情感分析1、数据预处理2、情感分析3、数据可视化 一、引言 前几天出了《航海王&#xff1…
阅读更多...
delete 清空表之后，磁盘空间未发生变化？

delete 清空表之后，磁盘空间未发生变化？

上篇文章结尾和小伙伴们留了一个小问题&#xff0c;就是关于 optimize table 命令&#xff0c;今天我想花点时间再来和小伙伴们聊一聊这个话题。 1. 删除空洞 1.1 案例展示 首先我们先来看这样一个例子。 我现在有一个名为 sakila 的数据库&#xff0c;该库中有一个 film 表…
阅读更多...
x宝评论抓取

x宝评论抓取

#某宝评论接口sign参数逆向 1.接口速览 多次请求发现&#xff0c;t为时间戳&#xff0c;sign为加密参数&#xff0c;盲猜和data、t有关&#xff0c;sign为32位&#xff0c;盲猜是字符串的32位的MD5 2.搜索js代码 这里为搜索的是appKey&#xff0c;就找到了sign&#xff0c;然…
阅读更多...
【CSS】常见的选择器

【CSS】常见的选择器

1.标签选择器 语法 标签 { }作用 标签选择器用于选择某种标签比如 选择p标签&#xff0c;并设置背景颜色 p { background-color:yellow; }例子 选择div标签&#xff0c;并将其字体大小设置为100px&#xff0c;字体设置为"微软雅黑"&#xff0c;文字颜色设置为r…
阅读更多...
UDP协议和TCP协议

UDP协议和TCP协议

目录 UDP TCP 通过序列号与确认应答提高可靠性 为什么TCP是三次握手 为什么是四次挥手 超时重传机制 流控制 利用窗口控制提高速度 窗口控制与重发控制 拥塞控制 延迟确认应答 捎带应答 UDP UDP是不具有可靠性的数据报协议。细微的处理它会交给上层的应用去完成。…
阅读更多...
从零开始，5分钟轻松实现Spring Boot与RabbitMQ的无缝集成

从零开始，5分钟轻松实现Spring Boot与RabbitMQ的无缝集成

&#x1f30f; 环境 docker v4.16.2springboot 2.7.0RabbitMQ 3.9.1 rabbitmq_delayed_message_exchange 3.9.0 ps&#xff1a;代码地址 gitee &#x1fa9c; 服务架构 使用maven多模块&#xff0c;将生产者、消费者分别以springboot项目启动&#xff0c;两者通过RabbitMQ…
阅读更多...
面试总结个人版

面试总结个人版

一、面试题 java 集合 &#xff0c; spring springmvc springboot springcloud 数据库相关的&#xff0c; redis 相关 &#xff0c;mq 相关 &#xff0c;结合业务的场景题 1、part one 集合 HashMap底层原理 HashMap是基于哈希表的Map接口的非同步实现。元素以键值对的形式存…
阅读更多...
AI-Prompt 1.0 版简介公测！你的AI提示词网站！

AI-Prompt 1.0 版简介公测！你的AI提示词网站！

提示词&#xff08;Prompt&#xff09; 是什么&#xff1f; 在 AI 大模型中&#xff0c;一个 prompt 是一个输入文本&#xff0c;用于触发模型生成输出。例如&#xff0c;当我们向一个 AI 大模型提交需求时&#xff0c;我们的需求就是一个 prompt。 在介绍产品之前&#xff0c;…
阅读更多...
CoreDX DDS应用开发指南（4）DDS实体h和主题

CoreDX DDS应用开发指南（4）DDS实体h和主题

6 DDS实体 DDS标准定义了一个体系结构，该体系结构表示构成DDS API实体的面向对象模型。这些实体充当中间件和应用软件之间的接口。为了开发支持DDS的应用程序，开发人员必须创建、交互并销毁这些DDS实体。 本章概述了DDS实体和相关概念。 6.1 DDS实体层次结构 构成DDS API的主…
阅读更多...
OpenELB 在 CVTE 的最佳实践

OpenELB 在 CVTE 的最佳实践

作者&#xff1a;大飞哥&#xff0c;视源电子股份运维工程师&#xff0c; KubeSphere 社区用户委员会广州站站长&#xff0c;KubeSphere Ambassador。 公司介绍 广州视源电子科技股份有限公司&#xff08;以下简称视源股份&#xff09;成立于 2005 年 12 月&#xff0c;旗下拥…
阅读更多...
[7]PCB设计实验｜认识常用元器件｜电容器｜19:00~19:30

[7]PCB设计实验｜认识常用元器件｜电容器｜19:00~19:30

目录 一、电容器的识别 电容的应用 1. 电容有通交流阻隔直流电的作用 2. 有滤波、耦合、旁路作用等 3. 有些电容是有极性&#xff0c;有些是没有极性 二、常见电容器 1. 贴片电容 a、材质瓷片 b、材质钽介质 c、材质电解质 2. 手插电容 a、瓷片电容 b、聚脂电容 …
阅读更多...
Windows命令行查找并kill进程及常用批处理命令汇总

Windows命令行查找并kill进程及常用批处理命令汇总

Windows命令行查找并kill进程及常用命令汇总 打开命令窗口 开始—->运行—->cmd&#xff0c;或者是 windowR 组合键&#xff0c;调出命令窗口。 cmd命令行杀死Windows进程方法 1、根据进程名称批量kill 1&#xff09;、执行tasklist|more检索进程 2&#xff09;、执…
阅读更多...
使用OpenAI创建对话式聊天机器人

使用OpenAI创建对话式聊天机器人

引言 在当今的技术世界中&#xff0c;人工智能&#xff08;AI&#xff09;的发展迅猛&#xff0c;为我们带来了许多令人兴奋的创新。其中&#xff0c;自然语言处理&#xff08;NLP&#xff09;领域的进展使得开发对话式聊天机器人成为可能。OpenAI是一家领先的人工智能研究实验…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站