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

这篇具有很好参考价值的文章主要介绍了算法提高-图论-单源最短路的综合应用。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

单源最短路的综合应用

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的买卖是连通的
算法提高-图论-单源最短路的综合应用文章来源地址https://www.toymoban.com/news/detail-509222.html

#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;
}

到了这里,关于算法提高-图论-单源最短路的综合应用的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法入门&图论】【模板】拓扑排序|【模板】单源最短路2 |最小生成树

    ✅作者简介:热爱后端语言的大学生,CSDN内容合伙人 ✨精品专栏:C++面向对象 🔥系列专栏:算法百炼成神 本专栏收录的均为牛客网的算法题目,内含链表、双指针、递归、动态规划、基本数据结构等算法思想的具体运用。牛客网不仅有大量的经典算法题目,也有大厂的面

    2024年02月03日
    浏览(45)
  • 【图论】单源最短路问题

    Dijkstra算法是一种单源最短路径算法,用于找出图中从一个源点到其他所有点的最短路径。该算法的原理是采用贪心策略,每次将距离源点最近的点加入到已确定最短路径的集合中,并更新其它节点的距离。具体实现过程如下: 初始化距离数组dist[],源点距离为0,其余点距离

    2024年02月13日
    浏览(39)
  • 【图论】单源最短路

    算法提高课笔记 最短路问题可以分为以下两类: 边权非负——朴素Dijkstra、堆优化Dijkstra 有负权边——Bellman-Ford、SPFA 热浪 原题链接 德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪!!! 他们的德克萨斯长角牛吃起来不错,可是它们并不是很擅长生产富含奶油的乳制品

    2024年02月14日
    浏览(43)
  • 【图论 单源最短路】100276. 最短路径中的边

    单源最短路 图论知识汇总 给你一个 n 个节点的无向带权图,节点编号为 0 到 n - 1 。图中总共有 m 条边,用二维数组 edges 表示,其中 edges[i] = [ai, bi, wi] 表示节点 ai 和 bi 之间有一条边权为 wi 的边。 对于节点 0 为出发点,节点 n - 1 为结束点的所有最短路,你需要返回一个长度

    2024年04月22日
    浏览(34)
  • 【单源最短路 图论】882. 细分图中的可到达节点

    视频算法专题 单源最短路 图论 给你一个无向图(原始图),图中有 n 个节点,编号从 0 到 n - 1 。你决定将图中的每条边 细分 为一条节点链,每条边之间的新节点数各不相同。 图用由边组成的二维数组 edges 表示,其中 edges[i] = [ui, vi, cnti] 表示原始图中节点 ui 和 vi 之间存在

    2024年04月10日
    浏览(42)
  • 第三章 图论 No.2单源最短路之虚拟源点,状压最短路与最短路次短路条数

    dp是特殊的最短路,是无环图(拓扑图)上的最短路问题 1137. 选择最佳线路 1137. 选择最佳线路 - AcWing题库 对于每组测试数据,该重置的数据要重置,我没有重置idx,导致TLE 处理反向建图,还有一种扩展做法:虚拟源点 设置虚拟源点,与每个起点之间连接边权为0的边 原问题

    2024年02月14日
    浏览(48)
  • 【算法】单源最短路径算法——Dijkstra算法

    迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。这是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用 贪心算法 的策略, 每次遍历到始点距离最

    2024年02月05日
    浏览(45)
  • 数据结构学习记录——图-最短路径问题(无权图单源最短路径算法、有权图单源最短路径算法、多源最短路径算法、Dijkstra(迪杰斯特拉)算法、Floyd算法)

    目录 问题分类  无权图单源最短路径算法 思路 伪代码 时间复杂度 代码实现(C语言) 有权图单源最短路径算法 Dijkstra(迪杰斯特拉)算法 伪代码  时间复杂度  代码实现(C语言) 多源最短路径算法 两种方法 Floyd算法 代码实现(C语言) 最短路径问题的抽象 在网络中,求

    2024年02月08日
    浏览(58)
  • C++算法:单源最短路径Dijkstra

    如果你有一份北京地图,想从中关村走到三元桥,那么怎样能找出实现这一目的的最短路径呢?一种可能的方法就是将这两点之间所有的路线都找出来,然后求出每条路线的距离,找出最短的路线。但是仔细想想我们就会发现这种办法几乎是不可行的,因为这样的路线太多了,

    2024年02月09日
    浏览(44)
  • 迪杰斯特拉算法 – 图的单源最短路径

    迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。迪杰斯特拉算法采

    2024年02月05日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包