- 王靖翔 的博客
图论模板(含洛谷题目)
- 2023-9-24 21:59:58 @
update 2023/9/29:更改 Prim 算法的遗漏点
最小生成树
题目:P3366 【模板】最小生成树
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, ans, cnt;
int fa[N];
struct node {
int x, y, len;
}e[N];
bool cmp(node a, node b) {
return a.len < b.len;
}
int dfs(int x) {
// return fa[x] == x ? x : dfs(fa[x]);
if (fa[x] == x) {
return x;
}
fa[x] = dfs(fa[x]);
return fa[x];
}
bool init() {
for (int i = 1; i <= m; i++) {
fa[i] = i;
}
}
void kruskal() {
for (int i = 1; i <= m; i++) {
int fx = dfs(e[i].x);
int fy = dfs(e[i].y);
if (fx != fy) {
fa[fx] = fy;
ans += e[i].len;
cnt++;
}
}
}
int main() {
cin >> n >> m;
init();
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].len);
}
sort(e+1, e+m+1, cmp);
kruskal();
if (cnt == n-1) {
cout << ans;
} else {
cout << "orz";
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 5010;
int G[N][N], vis[N], dis[N];
void init() {
memset(G, INF, sizeof(G));
memset(dis, INF, sizeof(dis));
}
void prim(int n) {
dis[1] = 0;
int ret = 0;
for (int i = 1; i <= n; i++) {
int mi = INF;
int id = -1;
for (int j = 1; j <= n; j++) {
if (vis[j] == 0 && dis[j] < mi) {
mi = dis[j];
id = j;
}
}
if (id == -1) {
printf("orz\n");
return;
}
ret += mi;
vis[id] = 1;
for (int j = 1; j <= n; j++) {
if (vis[j] == 0 && G[id][j] < dis[j]) {
dis[j] = G[id][j];
}
}
}
cout << ret;
}
int main() {
init();
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y, z;
cin >> x >> y >> z;
if (z < G[x][y]) {
G[x][y] = G[y][x] = z;
}
}
prim(n);
return 0;
}
最短路径
单源最短路模板(无题目)
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 5010;
int G[N][N], vis[N], dis[N];
void init() {
memset(G, INF, sizeof(G));
memset(dis, INF, sizeof(dis));
}
void dijkstra(int n) {
dis[1] = 0;
int ret = 0;
for (int i = 1; i <= n; i++) {
int mi = INF;
int id = -1;
for (int j = 1; j <= n; j++) {
if (vis[j] == 0 && dis[j] < mi) {
mi = dis[j];
id = j;
}
}
vis[id] = 1;
for (int j = 1; j <= n; j++) {
if (dis[id] + G[id][j] < dis[j]) {
dis[j] = dis[id] + G[id][j];
}
}
}
cout << dis[n];
}
int main() {
init();
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y, z;
cin >> x >> y >> z;
if (z < G[x][y]) {
G[x][y] = G[y][x] = z;
}
}
dijkstra(n);
return 0;
}
(普通版)
P3371 【模板】单源最短路径(弱化版)
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
// 定义边的结构体
struct Edge {
int to;
int weight;
};
// SPFA算法求解最短路径
vector<int> spfa(int n, int m, int s, const vector<vector<Edge>>& graph) {
// 初始化距离数组,默认为无穷大
vector<int> distance(n + 1, INT_MAX);
vector<bool> inQueue(n + 1, false); // 记录节点是否在队列中
// 使用队列保存需要进行松弛操作的节点
queue<int> q;
// 起始点入队列
q.push(s);
distance[s] = 0;
inQueue[s] = true;
// SPFA算法迭代
while (!q.empty()) {
int currNode = q.front();
q.pop();
inQueue[currNode] = false;
// 遍历当前节点的邻居节点
for (const Edge& edge : graph[currNode]) {
int nextNode = edge.to;
int nextDistance = distance[currNode] + edge.weight;
// 如果新的距离更小,则更新距离数组并将节点加入队列
if (nextDistance < distance[nextNode]) {
distance[nextNode] = nextDistance;
if (!inQueue[nextNode]) {
q.push(nextNode);
inQueue[nextNode] = true;
}
}
}
}
return distance;
}
int main() {
int n, m, s;
cin >> n >> m >> s;
// 初始化图的邻接表
vector<vector<Edge>> graph(n + 1);
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
// 添加边到邻接表中
graph[u].push_back({v, w});
}
// 调用SPFA算法求解最短路径
vector<int> shortestPaths = spfa(n, m, s, graph);
// 输出最短路径长度
for (int i = 1; i <= n; ++i) {
if (shortestPaths[i] == INT_MAX) {
cout << "2147483647 "; // 表示不可达
} else {
cout << shortestPaths[i] << " ";
}
}
cout << endl;
return 0;
}
(堆优化)
P4779 【模板】单源最短路径(标准版)
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
// 定义边的结构体
struct Edge {
int to;
int weight;
};
// 使用邻接表存储图
vector<vector<Edge>> graph;
// Dijkstra算法求解最短路径
vector<int> dijkstra(int n, int m, int s) {
// 初始化距离数组,默认为无穷大
vector<int> distance(n + 1, INT_MAX);
// 定义优先队列(最小堆),保存节点和当前距离
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// 将起始点放入队列中
pq.push(make_pair(0, s));
distance[s] = 0;
// 开始迭代
while (!pq.empty()) {
// 取出队列中距离最小的节点
int currNode = pq.top().second;
int currDistance = pq.top().first;
pq.pop();
// 如果当前距离大于已知最短路径,则继续下一个节点
if (currDistance > distance[currNode]) continue;
// 遍历当前节点的所有邻居节点
for (const Edge& edge : graph[currNode]) {
int nextNode = edge.to;
int nextDistance = currDistance + edge.weight;
// 如果新的距离更小,则更新距离数组并将节点放入队列中
if (nextDistance < distance[nextNode]) {
distance[nextNode] = nextDistance;
pq.push(make_pair(nextDistance, nextNode));
}
}
}
return distance;
}
int main() {
int n, m, s;
cin >> n >> m >> s;
// 初始化图的邻接表
graph.resize(n + 1);
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
// 添加边到邻接表中
graph[u].push_back({v, w});
}
// 调用Dijkstra算法求解最短路径
vector<int> shortestPaths = dijkstra(n, m, s);
// 输出最短路径长度
for (int i = 1; i <= n; ++i) {
if (shortestPaths[i] == INT_MAX) {
cout << "2147483647 "; // 表示不可达
} else {
cout << shortestPaths[i] << " ";
}
}
cout << endl;
return 0;
}