leetcode_day63

本文最后更新于 2024年7月27日上午

今日内容：

SPFA

无负权回路SPFA

题目

某国为促进城市间经济交流，决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市，通过道路网络连接，网络中的道路仅允许从某个城市单向通行到另一个城市，不能反向通行。

网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用；权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。

请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。如果最低运输成本是一个负数，它表示在遵循最优路径的情况下，运输过程中反而能够实现盈利。

城市 1 到城市 n 之间可能会出现没有路径的情况，同时保证道路网络中不存在任何负权回路。

输入描述

第一行包含两个正整数，第一个正整数 n 表示该国一共有 n 个城市，第二个整数 m 表示这些城市中共有 m 条道路。

接下来为 m 行，每行包括三个整数，s、t 和 v，表示 s 号城市运输货物到达 t 号城市，道路权值为 v （单向图）。

输出描述

如果能够从城市 1 到连通到城市 n，请输出一个整数，表示运输成本。如果该整数是负数，则表示实现了盈利。如果从城市 1 没有路径可达城市 n，请输出 "unconnected"。

思路

昨天使用Bellman_ford求解了该问题，SPFA为Bellman_ford的队列优化版。

上集提到，对全部边松弛一次，相当于对起点出发一条边的距离求了一次最短路。

那么在第二次全边松弛的时候，就可以不用再对起点出发一条边松弛了，直接拿结果即可。

所以，只需要对上一次松弛时更新过的节点作为出发点所连接的边进行松弛（carl说法）

就是继承上一次已经确定下来的点，再出发一条边。

优化的点在于，如果不使用队列优化，就按顺序去松弛，很容易松弛到未计算过节点延申出的边。而使用队列，则保证了在队列(是个数据结构能存就行，没有顺序要求)中的一定是计算过的节点，避免了无用的"松弛"

事实上，在未计算过的节点的延申边做的松弛无效，以初始的minDist举例比较好理解，如果节点未计算过，则其minDist为INT_MAX，如果对该点的边计算，结果肯定是有问题的。

所以，松弛n次得到距离n的点的最短路，已经不适用这里了，因为松弛已经不针对全图，次数的标准变得模糊。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, m;
    cin >> n >> m;
    vector<list<pair<int, int>>> grid(n + 1);
    for(int i = 0;i < m;i++) {
        int x, y, val;
        cin >> x >> y >> val;
        grid[x].push_back(pair<int, int>(y, val));
    }
    int start = 1;
    int end = n;
    vector<int> minDist(n + 1, INT_MAX);
    minDist[start] = 0;
    
    queue<int> q;
    q.push(start);
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        for(pair<int, int> &e : grid[cur]) {
            int x = cur, y = e.first, wt = e.second;
            if(minDist[y] > minDist[x] + wt) {
                minDist[y] = minDist[x] + wt;//更新更短的路径
                q.push(y);
            }
        }
    }
    if(minDist[end] == INT_MAX) cout << "unconnected";
    else cout << minDist[end] << endl;
    return 0;
}

负权回路SPFA

题目

然而，在评估从城市 1 到城市 n 的所有可能路径中综合政府补贴后的最低运输成本时，存在一种情况：图中可能出现负权回路。负权回路是指一系列道路的总权值为负，这样的回路使得通过反复经过回路中的道路，理论上可以无限地减少总成本或无限地增加总收益。为了避免货物运输商采用负权回路这种情况无限的赚取政府补贴，算法还需检测这种特殊情况。

请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。同时能够检测并适当处理负权回路的存在。

城市 1 到城市 n 之间可能会出现没有路径的情况

输入描述

第一行包含两个正整数，第一个正整数 n 表示该国一共有 n 个城市，第二个整数 m 表示这些城市中共有 m 条道路。

接下来为 m 行，每行包括三个整数，s、t 和 v，表示 s 号城市运输货物到达 t 号城市，道路权值为 v。

输出描述

如果没有发现负权回路，则输出一个整数，表示从城市 1 到城市 n 的最低运输成本（包括政府补贴）。如果该整数是负数，则表示实现了盈利。如果发现了负权回路的存在，则输出 "circle"。如果从城市 1 无法到达城市 n，则输出 "unconnected"。

思路

n-1次松弛就能找到所有点的最短路径，存在负权回路，当且仅当第n次松弛得到更短的路径。

所以只需要多松弛一次，如果出现更短，则有回路，如果没有，则没有负权回路。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, m;
    cin >> n >> m;
    vector<list<pair<int, int>>> grid(n + 1);
    for(int i = 0;i < m;i++) {
        int x, y, val;
        cin >> x >> y >> val;
        grid[x].push_back(pair<int, int>(y, val));
    }
    int start = 1;
    int end = n;
    vector<int> minDist(n + 1, INT_MAX);
    minDist[start] = 0;
    
    queue<int> q;
    q.push(start);
    vector<int> count(n + 1, 0);//新增代码，记录节点加入队列几次
    count[start]++;
    bool flag = false;
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        for(pair<int, int> &e : grid[cur]) {
            int x = cur, y = e.first, wt = e.second;
            if(minDist[y] > minDist[x] + wt) {
                minDist[y] = minDist[x] + wt;//更新更短的路径
                q.push(y);
                count[y]++;//新增代码
                if(count[y] == n) {//如果有节点加入队列超过n-1次，说明有负权回路
                    flag = true;
                    while(!q.empty()) q.pop();//清空队列
                    break;
                }
            }
        }
    }
    if(flag) cout << "circle";
    else if(minDist[end] == INT_MAX) cout << "unconnected";
    else cout << minDist[end] << endl;
    return 0;
}

单源有限最短路SPFA

题目

网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用；权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。

请计算在最多经过 k 个城市的条件下，从城市 src 到城市 dst 的最低运输成本。

输入描述

第一行包含两个正整数，第一个正整数 n 表示该国一共有 n 个城市，第二个整数 m 表示这些城市中共有 m 条道路。

接下来为 m 行，每行包括三个整数，s、t 和 v，表示 s 号城市运输货物到达 t 号城市，道路权值为 v。

最后一行包含三个正整数，src、dst、和 k，src 和 dst 为城市编号，从 src 到 dst 经过的城市数量限制。

输出描述

输出一个整数，表示从城市 src 到城市 dst 的最低运输成本，如果无法在给定经过城市数量限制下找到从 src 到 dst 的路径，则输出 "unreachable"，表示不存在符合条件的运输方案。

思路

题目的不同点在于，有了途径城市数量限制。也就是从一个点出发几条边有限制，也就是松弛次数有限制，那么针对次数过少，就得找到n-1次松弛前多种可能中最短的一条；次数过多，就得多走负权回路降本。

控制次数，可以使用层序的思想(或者叫写法)，而且还需要控制minDist的更新，由于SPFA的原写法可能在一个循环内更新了多次同一个值，这就无法控制中间节点数量了，得每一次都完全依赖前一轮循环的计算结果，避免超限；而选择更短的路，可以直接使用SPFA的原写法逻辑。

优化：对于同一层的节点，可能会有相互通的道路，这条路可以走，但是对于已经处理过的同一层节点就不需要重复入队了。开一个bool used数组记录本层哪些节点已经处理过，但是松弛仍需进行，只是不再入队。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<list<pair<int, int>>> grid(n + 1);
    for(int i = 0;i < m;i++) {
        int x, y, wt;
        cin >> x >> y >> wt;
        grid[x].push_back(pair<int, int>(y, wt));
    }
    int start, end, limit;
    cin >> start >> end >> limit;
    limit++;//经过限制->步数限制
    vector<int> minDist(n + 1, INT_MAX);
    vector<int> copy(n + 1);
    minDist[start] = 0;
    queue<int> q;
    q.push(start);
    int size;
    while(limit-- && !q.empty()) {
        copy = minDist;
        size = q.size();
        vector<bool> used(n + 1, false);
        while(size--) {
            int cur = q.front();
            q.pop();
            for(pair<int, int> & e : grid[cur]) {
                int y = e.first;
                int wt = r.second;
                if(minDist[y] > minDist[cur] + wt) {
                    minDist[y] = minDist[cur] + wt;
                    if(used[y]) continue;//跳过同层已处理节点
                    used[y] = true;
                    q.push(y);
                }
                
			}
		}
    }
    if(minDist[end] == INT_MAX) cout << "unconnctable" << endl;
    else cout << minDist[end] << endl;
}

#leetcode

leetcode_day63

https://novelyear.github.io/2024/07/25/leetcode-day63/

作者

Leoo Yann

更新于

2024年7月27日

许可协议

leetcode_day64 上一篇

leetcode_day62 下一篇