次小生成树

口述思路:

首先从原图得到最小生成树(这里用的kruskal算法). 显然, 这个最小生成树构成一个新图.

对于原图中的每一个非树边uv, 将其加入新图. 则在新图中会形成环(因为u到v的路径不止一条了).

在新图中, 深度优先搜索从u到v的路径, 用两个变量分别记录最大权值和次大权值.

最后, 对比最大权值和uv路径本身的权值, 如果相等说明MST不唯一. 如果大于说明用uv替换最大权边后总权重增大, 可能为次小生成树. 如果小于则无法替换, 因为会破坏最小生成树.

所以, 判断MST是否唯一的方法已经得到了.

在此基础上, 若想得到严格次小生成树, 有两种情况:

首先是当uv权重等于最大边权. 此时用uv替换次大权边, 然后记录此时的总权重.

其次是当uv权重大于最大边权. 此时直接用uv替换最大权边, 记录总权重.

最后所有替换后总权重取最小.

在实现上依旧有很多细节问题. 首先是最小生成树, 一套连招没什么好说的.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

struct Edge {
	int f, t, cost;
	bool used;
	Edge(int f, int t, int c) : f(f), t(t), cost(c), used(false) {}
	bool operator<(const Edge& e) {
		return this->cost < e.cost;
	}
};

class Set {
public:
	std::vector<int> parent;

	Set(int n) : parent(n + 1) {
		for (int i = 0; i < parent.size(); i++) {
			parent[i] = i;
		}
	}

	int find(int index) {
		int root = parent[index];
		while (root != parent[root]) {
			root = parent[root];
		}
		return root;
	}

	void unite(int x, int y) {
		int xRoot = find(x);
		int yRoot = find(y);
		if (xRoot == yRoot) return;
		parent[yRoot] = xRoot;
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}
};


int main() {
	int n, m;
	std::cin >> n >> m;

	std::vector<Edge> edges;

	for (int i = 0; i < m; i++) {
		int u, v, w;
		std::cin >> u >> v >> w;
		edges.push_back({ u, v, w });
	}

	std::sort(edges.begin(), edges.end());

	std::vector<std::vector<std::pair<int, int>>> graph(n + 1);
	Set set(n);
	int count = 0, total = 0;
	for (auto& edge : edges) {
		if (!set.same(edge.f, edge.t)) {
			set.unite(edge.f, edge.t);
			++count;
			total += edge.cost;
			edge.used = true;
			graph[edge.f].emplace_back(edge.t, edge.cost);
			graph[edge.t].emplace_back(edge.f, edge.cost);
			if (count == n - 1) {
				break;
			}
		}
	}

	std::unordered_set<int> roots;
	for (int i = 1; i <= n; i++) {
		roots.insert(set.find(i));
	}
	if (roots.size() > 1) {
		std::cout << "NO MST\n" << roots.size();
		return 0;
	}

	return 0;
}

基于最小生成树, 我们得到了一个新图, 在代码里是graph变量. 仅包含了最小生成树的路径.

在这个graph中, 用DFS寻找从u到v的路径上的最大边权和次大边权.

bool DFS(int u, int target, int fa, int curr_max1, int curr_max2, int& max1, int& max2, const std::vector<std::vector<std::pair<int, int>>>& graph) {
	if (u == target) {
		max1 = curr_max1;
		max2 = curr_max2;
		return true;
	}
	for (auto& e : graph[u]) {
		int v = e.first;
		int w = e.second;
		if (v == fa) continue;
		int new_max1 = curr_max1, new_max2 = curr_max2;
		if (w > new_max1) {
			new_max2 = new_max1;
			new_max1 = w;
		}
		else if (w < new_max1 && w > new_max2) {
			new_max2 = w;
		}
		if (DFS(v, target, u, new_max1, new_max2, max1, max2, graph)) {
			return true;
		}
	}
	return false;
}

void get_max_edge(int u, int v, int& max1, int& max2, const std::vector<std::vector<std::pair<int, int>>>& graph) {
	max1 = max2 = -1;
	DFS(u, v, -1, -1, -1, max1, max2, graph);
}

细节很多. fa代表前驱节点. 仔细心算一下就可以知道, 我们对new_max1和new_max2的更新保证了二者除了一开始都为-1, 其余情况都不可能相等. 只要new_max2不为-1. 说明必定有次小边权. 如果new_max2为-1, 说明没有次小边权.

之后是得到次小生成树:

bool unique = true;
int second = int(static_cast<unsigned int>(-1) >> 1);
for (auto& edge : edges) {
	if (!edge.used) {
		int u = edge.f, v = edge.t, w = edge.cost;
		int max1, max2;
		get_max_edge(u, v, max1, max2, graph);
		if (unique && w == max1) {
			unique = false;
		}
		if (max1 != -1 && w > max1) {
			second = std::min(second, total - max1 + w);
		}
		if (max2 != -1 && w > max2) {
			second = std::min(second, total - max2 + w);
		}
	}
}

根据我们前面说的, w == 最大边权的时候, MST不唯一. 对second的更新非常关键, 但我个人想不清楚这玩意, 想了半天...只能说就是这样写的吧.

最短路径

单源: 求某个点到其他点的最短路径

image

从A出发, 看A到B的距离是否小于当前数组中记录的距离, 如果小于, 更新距离, 记录前驱, 并将边加入最小堆.

之后的循环, 从最小堆中取出一个元素, 看该节点是否被访问过. 如果访问过, 跳过; 如果没访问过, 重复一次对A做过的操作.

一道题目的参考代码:

#include <iostream>
#include <queue>
#include <vector>
#include <map>

struct Edge {
	int dest, len, cost;
	Edge(int d, int l, int c) : dest(d), len(l), cost(c){}
};

using Graph = std::vector<std::vector<Edge>>;

struct cmp {
	bool operator()(const Edge& a, const Edge& b) {
		return a.len > b.len;
	}
};

void Dijkstra(int s, const Graph& graph, std::vector<int>& dist, std::vector<int>& cost) {
	std::priority_queue<Edge, std::vector<Edge>, cmp> pq;

	pq.emplace(s, 0, 0);
	dist[s] = 0;

	while (!pq.empty()) {
		Edge e = pq.top();
		pq.pop();

		int node = e.dest;	//当前节点
		int len = e.len;	//当前节点累计权值
		int curr_cost = e.cost;	//当前节点累计费用

		if (!(len > dist[node])) {
			for (auto& edge : graph[node]) {
				if (dist[edge.dest] > len + edge.len) {
					dist[edge.dest] = len + edge.len;
					cost[edge.dest] = curr_cost + edge.cost;
					pq.emplace(edge.dest, dist[edge.dest], cost[edge.dest]);
				}
				else if (dist[edge.dest] == len + edge.len) {
					if (curr_cost + edge.cost < cost[edge.dest]) {
						cost[edge.dest] = curr_cost + edge.cost;
						pq.emplace(edge.dest, dist[edge.dest], cost[edge.dest]);
					}
				}
			}
		}
	}
}

int main() {
	int N, M, S, D;
	std::cin >> N >> M >> S >> D;

	constexpr int INTMAX = (int)((unsigned int)-1 >> 1);

	Graph graph(N);

	for (int i = 0; i < M; i++) {
		int u, v, l, c;
		std::cin >> u >> v >> l >> c;
		graph[u].push_back({ v, l, c });
		graph[v].push_back({ u, l, c });
	}

	std::vector<int> dist(N, INTMAX), cost(N, 0);

	Dijkstra(S, graph, dist, cost);

	std::cout << dist[D] << " " << cost[D];

	return 0;
}

重点是: 需要对边进行累计. 并且, 使用最小堆的情况下, 是不需要visited数组的. 别问为什么, 我也不太懂.

‍

多源: 求所有点互相之间的最短路径.

显然可以用dijkstra重复多次实现, 但无法处理负权边.

可以用floyd算法, 整体比dijkstra简单, 但是复杂度高, O(n3).

口述floyd思路:

image

首先为图建立一个邻接矩阵dist. 节点到自己的距离为0, 没路就为正无穷, 有路就为权重.

image

之后, 建立一个next矩阵. 代表从i到j的下一个节点是谁. 显然, 一开始的时候, 有路径的话就是j, 没路径就没有.

image

算法的思路就是: 每次选取一个中间节点k, 看看dist矩阵中存储的从i到j的距离是否大于从i到k再从k到j的距离. 如果是, 则认为从i到j的路径的下一个节点是k. dist也更新为从i到k的权重加上从k到j的权重.

image 
#include <iostream>
#include <vector>

using Graph = std::vector<std::vector<int>>;

int main() {
	int N, M;
	std::cin >> N >> M;

	constexpr int INTMAX = (int)((unsigned int)-1 >> 1);

	Graph dist(N + 1, std::vector<int>(N + 1, INTMAX));
	Graph next(N + 1, std::vector<int>(N + 1, 0));

	for (int i = 0; i < M; i++) {
		int u, v, l;
		std::cin >> u >> v >> l;
		if (dist[u][v] > l) {
			dist[u][v] = l;
			dist[v][u] = l;
			next[u][v] = v;
			next[v][u] = u;
		}
	}

	for (int i = 0; i <= N; i++) {
		dist[i][i] = 0;
		next[i][i] = i;
	}

	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (dist[i][k] != INTMAX && dist[k][j] != INTMAX) {
					if (dist[i][j] > dist[i][k] + dist[k][j]) {
						dist[i][j] = dist[i][k] + dist[k][j];
						next[i][j] = next[i][k];
					}
				}
			}
		}
	}

	std::vector<int> result(N + 1, -INTMAX);
	int minDist = INTMAX, index = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (dist[i][j] == INTMAX) {
				std::cout << 0;
				return 0;
			}
			result[i] = std::max(result[i], dist[i][j]);
		}
		if (result[i] < minDist) {
			minDist = result[i];
			index = i;
		}
	}

	std::cout << index << " " << minDist;

	return 0;
}
image

拓扑排序与关键路径

Kahn算法. 基于入度

首先将入度为0的节点加入队列.

循环开始. 出队, 被其链接的节点入度减一, 判断入度是否为0, 如果为零则入队.

出队的顺序就是最后的结果.

image​

例: 判断有无循环依赖.

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

using Graph = std::vector<std::vector<int>>;

int main() {
	int N;
	std::cin >> N;
	std::vector<int> inDegree(N + 1, 0);
	Graph graph(N + 1);

	for (int i = 1; i <= N; i++) {
		int K;
		std::cin >> K;
		for (int j = 0; j < K; j++) {
			int x;
			std::cin >> x;
			graph[i].push_back(x);
			++inDegree[x];
		}
	}

	std::queue<int> q;
	for (int i = 1; i <= N; i++) {
		if (inDegree[i] == 0) {
			q.push(i);
		}
	}
	int cnt = 0;
	while (!q.empty()) {
		int node = q.front();
		q.pop();
		cnt++;
		for (auto& dest : graph[node]) {
			inDegree[dest]--;
			if (inDegree[dest] == 0) {
				q.push(dest);
			}
		}
	}
	if (cnt == N) {
		std::cout << 1;
	}
	else std::cout << 0;
}

按照这个思路, 可以知道逆拓扑排序的求法, 即基于出度. 此处不再赘述.

求关键路径(即耗时最长的路径), 求每个节点的最早发生时间和最晚发生时间.

image​

先求最早发生时间. 在拓扑排序的基础上. 按顺序遍历拓扑排序. 创建一个数组用于存储每个节点的最早开始时间, 初始为0.

对于拓扑排序的每一个节点, 都有一个for循环遍历其邻接的节点.

循环开始, 比较"当前节点的最早开始时间加上路径权重"与"邻接节点的最早开始时间". 取大的作为邻接节点的最早开始时间.

再求最晚发生时间. 创建数组存储, 初始化为最后那个节点的最早开始时间. 逆序遍历拓扑排序.

对于每一个节点, 都有一个for循环遍历邻接节点.

循环开始, 比较"当前节点的最晚开始时间"与"邻接节点的最晚开始时间减去路径权重". 取小的作为邻接节点的最晚开始时间.

(注意, 路径是从邻接节点指向当前节点. 作为对比, 求最早发生时间的时候, 路径是从当前节点指向邻接节点).

最后, 从拓扑排序的第一个节点开始遍历.

遍历该节点的邻接节点, 用"该邻接节点的最晚开始时间"减去"该节点的最早开始时间", 如果等于"路径权重", 说明是关键路径.

std::vector<int> ve(N + 1, 0);
for (int i = 0; i < topo.size(); i++) {
	for (auto& p : graph[topo[i]]) {
		int node = p.first;
		int len = p.second;
		if (ve[node] < ve[topo[i]] + len) {
			ve[node] = ve[topo[i]] + len;
		}
	}
}
std::vector<int> vl(N + 1, ve[topo[N - 1]]);
for (int i = topo.size()-1; i >= 0; i--) {
	for (auto& p : graph[topo[i]]) {
		int node = p.first;
		int len = p.second;
		if (vl[topo[i]] > vl[node] - len) {
			vl[topo[i]] = vl[node] - len;
		}
	}
}

std::cout << ve[topo[N - 1]] << "\n";
for (int i = 0; i < topo.size(); i++) {
	for (auto& p : graph[topo[i]]) {
		int node = p.first;
		int len = p.second;
		if (vl[node] - ve[topo[i]] == len) {
			std::cout << topo[i] << "->" << node << "\n";
		}
	}
}