链式前向星-学习笔记

目录

• 1.存图的方式列举
• 2.存图方式的优劣对比
• 3.为什么要用链式前向星
• 4.如何写链式前向星
• 5.例题

存图的方式列举

比较主要的的就是邻接矩阵和邻接表，当然有一种特别的——今天的主角：链式前向星。

存图方式的优劣对比

如果是稠密图的话，通常使用邻接矩阵，而稀疏图，大多使用邻接表。然而，邻接矩阵就TLE了，邻接表就MLE了。啊，好崩溃啊！

有没有一种又快又省空间的存图方式啊！天无绝人之路，有，它就是拥有霸气名字的链式前向星。正如其名，它是一种向前的、用数组模拟链表的数据结构，而且同样适用于稀疏、稠密图。（我的救星大人

为什么要用链式前向星

因为它又快又省，并且还有一堆算法依赖它（例如：SPFA、Bellman-Ford、Kruskal、Prim等）。

如何写链式前向星

基本形式如下：

int v[2*MAXN],w[2*MAXN],Next[2*MAXN],head[2*MAXN],idx;
void add(int ui , int vi , int wi){
    v[++idx]=vi; //从1开始存图是为了有些题目0的特判
    w[idx]=wi;
    Next[idx]=head[ui];
    head[u]=idx;
}

update：2024/3/24 14:11

链式前向星如果要判断自环和重边的话需要重写add()函数如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
using namespace std;

const int MAXN = 100010;
const int INF = 0x3f3f3f3f;
int head[MAXN], ver[MAXN * 2], edge[MAXN * 2], Next[MAXN * 2];
int d[MAXN];
bool vis[MAXN];
int n, m, s, tot;
map<pair<int, int>, int> weight;

void add(int x, int y, int z) {
    if (x == y) return; 
    if (weight.find({x, y}) != weight.end()) {
        if (z < weight[{x, y}]) {
            weight[{x, y}] = z;
            for (int i = head[x]; i; i = Next[i]) {
                if (ver[i] == y) {
                    edge[i] = z;
                    break;
                }
            }
        }
    } else {
        weight[{x, y}] = z;
        ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
    }
}

例题

道路重建 洛谷P3905

题目描述

从前，在一个王国中，在 \(n\) 个城市间有 \(m\) 条道路连接，而且任意两个城市之间至多有一条道路直接相连。在经过一次严重的战争之后，有 \(d\) 条道路被破坏了。国王想要修复国家的道路系统，现在有两个重要城市 \(A\) 和 \(B\) 之间的交通中断，国王希望尽快的恢复两个城市之间的连接。你的任务就是修复一些道路使 \(A\) 与 \(B\) 之间的连接恢复，并要求修复的道路长度最小。

输入格式

输入文件第一行为一个整数 \(n\ (2<n\le 100)\)，表示城市的个数。这些城市编号从 \(1\) 到 \(n\)。

第二行为一个整数 \(m\ (n-1\le m\le \dfrac{1}{2}n(n-1))\)，表示道路的数目。

接下来的 \(m\) 行，每行 \(3\) 个整数 \(i,j,k\ (1 \le i,j \le n,i\neq j,0<k \le 100)\)，表示城市 \(i\) 与 \(j\) 之间有一条长为 \(k\) 的道路相连。

接下来一行为一个整数 \(d\ (1\le d\le m)\)，表示战后被破坏的道路的数目。在接下来的 \(d\) 行中，每行两个整数 \(i\) 和 \(j\)，表示城市 \(i\) 与 \(j\) 之间直接相连的道路被破坏。

最后一行为两个整数 \(A\) 和 \(B\)，代表需要恢复交通的两个重要城市。

输出格式

输出文件仅一个整数，表示恢复 \(A\) 与 \(B\) 间的交通需要修复的道路总长度的最小值。

样例 #1

样例输入 #1

3
2
1 2 1
2 3 2
1
1 2
1 3

样例输出 #1

1

这里就不放代码了，同志请自己加油！（提示：\(n \le 100\)的数据量为什么不试试floyd+链式前向星呢）