2024-05-19发表2024-08-24更新studynotes4 分钟读完 (大约606个字)

Tarjan算法介绍

算法分析

Tarjan算法用于在有向图中寻找强连通分量（SCC）。强连通分量是指在一个子图中，任意两个顶点之间都存在路径。Tarjan算法基于深度优先搜索（DFS），其时间复杂度为\(O(V + E)\)，其中\(V\)是顶点数，\(E\)是边数。

算法的核心思想是通过DFS遍历图，并使用一个栈来跟踪访问路径。每个节点都有一个唯一的索引和一个低链接值，低链接值表示该节点或其子节点能够访问的最早节点。

伪代码

以下是Tarjan算法的伪代码：

function tarjanSCC(graph):
    index = 0
    stack = []
    for each vertex v in graph:
        if v.index is undefined:
            strongConnect(v)

function strongConnect(v):
    v.index = index
    v.lowlink = index
    index += 1
    stack.push(v)
    v.onStack = true

    for each (v, w) in v.edges:
        if w.index is undefined:
            strongConnect(w)
            v.lowlink = min(v.lowlink, w.lowlink)
        else if w.onStack:
            v.lowlink = min(v.lowlink, w.index)

    if v.lowlink == v.index:
        start a new SCC
        repeat
            w = stack.pop()
            w.onStack = false
            add w to current SCC
        until w == v

C++代码

以下是Tarjan算法的C++实现：

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Graph {
    int V;
    vector<int> *adj;
    void SCCUtil(int u, int disc[], int low[], stack<int> *st, bool stackMember[]);

public:
    Graph(int V);
    void addEdge(int v, int w);
    void SCC();
};

Graph::Graph(int V) {
    this->V = V;
    adj = new vector<int>[V];
}

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w);
}

void Graph::SCCUtil(int u, int disc[], int low[], stack<int> *st, bool stackMember[]) {
    static int time = 0;
    disc[u] = low[u] = ++time;
    st->push(u);
    stackMember[u] = true;

    for (int i : adj[u]) {
        if (disc[i] == -1) {
            SCCUtil(i, disc, low, st, stackMember);
            low[u] = min(low[u], low[i]);
        } else if (stackMember[i]) {
            low[u] = min(low[u], disc[i]);
        }
    }

    int w = 0;
    if (low[u] == disc[u]) {
        while (st->top() != u) {
            w = st->top();
            cout << w << " ";
            stackMember[w] = false;
            st->pop();
        }
        w = st->top();
        cout << w << "\n";
        stackMember[w] = false;
        st->pop();
    }
}

void Graph::SCC() {
    int *disc = new int[V];
    int *low = new int[V];
    bool *stackMember = new bool[V];
    stack<int> *st = new stack<int>();

    for (int i = 0; i < V; i++) {
        disc[i] = -1;
        low[i] = -1;
        stackMember[i] = false;
    }

    for (int i = 0; i < V; i++) {
        if (disc[i] == -1) {
            SCCUtil(i, disc, low, st, stackMember);
        }
    }
}

int main() {
    Graph g(5);
    g.addEdge(1, 0);
    g.addEdge(0, 2);
    g.addEdge(2, 1);
    g.addEdge(0, 3);
    g.addEdge(3, 4);

    cout << "Strongly Connected Components in the given graph are:\n";
    g.SCC();

    return 0;
}

以上代码定义了一个图类 Graph，并实现了Tarjan算法来寻找图中的强连通分量。Graph类包含添加边的方法 addEdge 和执行Tarjan算法的方法 SCC。SCCUtil 是一个辅助函数，用于递归地执行深度优先搜索并计算每个节点的 disc 和 low 值。

2024-04-27发表2024-08-24更新studynotes5 分钟读完 (大约816个字)

MST-学习笔记

最小生成树（Minimum Spanning Tree, MST）是在一个加权无向图中寻找一个边的子集，使得这个子集构成的树包含图中的所有顶点，并且边的权重之和最小。

1.切分定理

切分定理是最小生成树算法的理论基础。它指出：

如果将图中的节点分为两部分，那么连接这两部分的最小权重的边必定属于图的最小生成树。

这个定理是Prim算法和Kruskal算法正确性的保证。

2. Kruskal算法

时间复杂度

Kruskal算法的时间复杂度主要由排序边的操作决定，为 \(O(E \log E)\)，其中 \(E\) 是图中边的数量。在边排序之后，算法需要进行并查集操作，时间复杂度为 \(O(E \alpha(V))\)，其中 \(\alpha\) 是阿克曼函数的反函数，对于所有实际的输入值几乎可以认为是常数。

核心伪代码

KRUSKAL(G):
1. A = ∅
2. 对每个顶点 v ∈ G.V:
3.     MAKE-SET(v)
4. 将 G.E 中的边按权重从小到大排序
5. for each edge (u, v) ∈ G.E ordered by increasing weight:
6.     if FIND-SET(u) ≠ FIND-SET(v):
7.         A = A ∪ {(u, v)}
8.         UNION(u, v)
9. return A

示例代码

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;

const int maxn = 2005;
struct Edge {
    int x, y, z;
} e[maxn * maxn];
int fa[maxn];

int findset(int x) {
    if (x == fa[x]) return x;
    return fa[x] = findset(fa[x]);
}

bool cmp(const Edge& a, const Edge& b) {
    return a.z < b.z;
}

int main() {
    int n; scanf("%d", &n);
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            scanf("%d", &e[++cnt].z);
            e[cnt].x = i - 1;
            e[cnt].y = j;
        }
    }

    for (int i = 1; i <= n; i++) fa[i] = i;

    ll ans = 0;
    sort(e + 1, e + cnt + 1, cmp);
    int num = 0;
    for (int i = 1; i <= cnt; i++) {
        int x = e[i].x, y = e[i].y, w = e[i].z;
        int rx = findset(x), ry = findset(y);
        if (rx != ry) {
            fa[rx] = ry;
            num++;
            ans += w;
            if (num == n - 1) break;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

3. Prim算法

时间复杂度

Prim算法的时间复杂度依赖于使用的数据结构。使用优先队列实现时，时间复杂度为 \(O(E \log V)\)，其中 \(V\) 是顶点数，\(E\) 是边数。

核心伪代码

PRIM(G, r):
1. for each u ∈ G.V:
2.     u.key = ∞
3.     u.parent = NIL
4. r.key = 0
5. Q = G.V
6. while Q ≠ ∅:
7.     u = EXTRACT-MIN(Q)
8.     for each v adjacent to u:
9.         if v ∈ Q and w(u, v) < v.key:
10.            v.parent = u
11.            v.key = w(u, v)

示例代码

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef pair<int, int> pii; // first: weight, second: vertex

vector<vector<pii>> adj; // adjacency list

int prim(int start, int n) {
    vector<int> key(n, INT_MAX);
    vector<bool> inMST(n, false);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    key[start] = 0;
    pq.push({0, start});

    int mst_cost = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (inMST[u]) continue;
        inMST[u] = true;
        mst_cost += key[u];

        for (auto &[cost, v] : adj[u]) {
            if (!inMST[v] && cost < key[v]) {
                key[v] = cost;
                pq.push({cost, v});
            }
        }
    }

    return mst_cost;
}

int main() {
    int n, m;
    cin >> n >> m;
    adj.resize(n);

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({w, v});
        adj[v].push_back({w, u});
    }

    int start_vertex = 0; // assuming the vertices are 0-indexed
    cout << "Cost of MST: " << prim(start_vertex, n) << endl;

    return 0;
}

这段代码使用了C++的STL容器，如 vector 和 priority_queue，来实现Prim算法。这里的 priority_queue 用于维护一个按边权重排序的顶点集合，以便每次都能从中取出当前最小边权的顶点。

2024-03-25发表2024-08-24更新studynotes4 分钟读完 (大约599个字)

AC自动机-学习笔记

AC自动机（Aho-Corasick自动机）是一种用于字符串搜索的算法，可以在一组字符串中快速查找一个或多个子串。这种算法特别适合于在大量文本中查找多个模式。

基本概念

AC自动机结合了两种算法：Trie树和KMP算法。

Trie树：用于存储多个字符串的数据结构，每个节点代表一个字符，从根到某一节点的路径代表一个字符串。
KMP算法：一种字符串搜索算法，可以在不回溯文本指针的情况下，通过回溯模式指针来提高搜索效率。

构建AC自动机

构建AC自动机分为三个步骤：

构建Trie树：将所有模式串插入Trie树中。
构建失败指针：类似于KMP中的next数组，当节点匹配失败时，失败指针指向一个最长可匹配的后缀节点。
搜索状态转移：利用Trie树和失败指针进行状态转移，匹配文本串。

构建Trie树

struct TrieNode {
    TrieNode* children[26];
    TrieNode* fail; // 失败指针
    int end; // 标记字符串结束
    TrieNode() : fail(nullptr), end(0) {
        memset(children, 0, sizeof(children));
    }
};

void insert(TrieNode* root, const string& word) {
    TrieNode* node = root;
    for (char c : word) {
        if (!node->children[c - 'a']) {
            node->children[c - 'a'] = new TrieNode();
        }
        node = node->children[c - 'a'];
    }
    node->end += 1; // 标记单词结束
}

构建失败指针

void buildFailPointer(TrieNode* root) {
    queue<TrieNode*> q;
    root->fail = nullptr;
    q.push(root);

    while (!q.empty()) {
        TrieNode* current = q.front();
        q.pop();

        for (int i = 0; i < 26; ++i) {
            TrieNode* child = current->children[i];
            if (child) {
                TrieNode* fail = current->fail;
                while (fail && !fail->children[i]) {
                    fail = fail->fail;
                }
                child->fail = fail ? fail->children[i] : root;
                q.push(child);
            }
        }
    }
}

搜索状态转移

void search(TrieNode* root, const string& text) {
    TrieNode* node = root;
    for (char c : text) {
        while (node && !node->children[c - 'a']) {
            node = node->fail; // 失败指针回溯
        }
        node = node ? node->children[c - 'a'] : root;
        for (TrieNode* temp = node; temp; temp = temp->fail) {
            if (temp->end) {
                // 找到一个模式串
            }
        }
    }
}

总结

AC自动机是一种高效的多模式字符串搜索算法，通过结合Trie树和KMP算法的优点，能够在 \(O(n)\)的时间复杂度内完成搜索。在实际应用中，AC自动机常用于文本过滤、搜索引擎等领域。

以上就是AC自动机的基本介绍和实现。希望这份学习笔记对你有所帮助！

2024-03-24发表2024-08-24更新studynotes6 分钟读完 (大约896个字)

Bellman-Ford-学习笔记

Bellman-Ford算法是一种图论中的算法，用于在带权图中找到单源最短路径，即从一个顶点到图中所有其他顶点的最短路径。与Dijkstra算法相比，Bellman-Ford算法的一个显著特点是它能够处理图中包含负权边的情况。

算法原理

Bellman-Ford算法通过对所有边的多次迭代来逐步减小从源点到所有点的估计距离，直到这些估计距离反映出真实的最短路径长度。算法的核心思想是动态规划。

算法步骤

初始化：设置源顶点到自己的最短距离为 \(0\)，到其他所有顶点的最短距离为无穷大。
松弛操作：对图中的所有边进行 \(V-1\) 次迭代（\(V\) 是顶点数），每次迭代中，更新图中所有边的两个顶点之间的最短距离。
检测负权回路：在第V次迭代中检查是否还能更新最短距离，如果能，则图中存在负权回路。

C++实现

下面是Bellman-Ford算法的一个基本C++实现示例：

#include <iostream>
#include <vector>
#include <limits>
using namespace std;
struct Edge {
	int src, dest, weight;
};
struct Graph {
	int V, E;
	vector<Edge> edges;
	Graph(int V, int E) {
		this->V = V;
		this->E = E;
	}
	void addEdge(int src, int dest, int weight) {
		edges.push_back({src, dest, weight});
	}
};
void BellmanFord(Graph& graph, int src) {
	int V = graph.V;
	int E = graph.E;
	vector<int> dist(V, numeric_limits<int>::max());
	dist[src] = 0;
	for (int i = 1; i <= V - 1; i++) {
		for (int j = 0; j < E; j++) {
			int u = graph.edges[j].src;
			int v = graph.edges[j].dest;
			int weight = graph.edges[j].weight;
			if (dist[u] != numeric_limits<int>::max() && dist[u] + weight < dist[v])
				dist[v] = dist[u] + weight;
		}
	}
	for (int i = 0; i < E; i++) {
		int u = graph.edges[i].src;
		int v = graph.edges[i].dest;
		int weight = graph.edges[i].weight;
		if (dist[u] != numeric_limits<int>::max() && dist[u] + weight < dist[v]) {
			cout << "Graph contains negative weight cycle" << endl;
			return;
		}
	}
	cout << "Vertex Distance from Source\n";
	for (int i = 0; i < V; ++i)
		cout << i << "\t\t" << dist[i] << endl;
}
int main() {
	int V = 5; // 顶点数
	int E = 8; // 边数
	Graph graph(V, E);
	// 添加边 src, dest, weight
	graph.addEdge(0, 1, -1);
	graph.addEdge(0, 2, 4);
	graph.addEdge(1, 2, 3);
	graph.addEdge(1, 3, 2);
	graph.addEdge(1, 4, 2);
	graph.addEdge(3, 2, 5);
	graph.addEdge(3, 1, 1);
	graph.addEdge(4, 3, -3);
	BellmanFord(graph, 0);
	return 0;
}

注意事项

Bellman-Ford算法的时间复杂度为 \(O(VE)\)，对于稠密图可能不够高效。
算法能够检测图中是否存在负权重的环。如果在执行完所有松弛操作后，仍可以继续松弛，说明存在从源点可达的负权重环，因此无法找到最短路径。

扩展阅读

应用场景：Bellman-Ford算法不仅可以用来计算最短路径，还可以用来检测负权回路，这在某些应用中非常有用，比如在经济学或网络路由优化中。
算法优化：尽管标准的Bellman-Ford算法时间复杂度较高，但可以通过各种技巧进行优化，例如，如果一次遍历中没有任何更新，则可以提前终止算法。
与Dijkstra算法的比较：Dijkstra算法通常更快，但它不能处理负权边。因此，选择哪种算法取决于具体问题的需求。

结语

Bellman-Ford算法是解决带负权图中单源最短路径问题的一个强大工具。虽然它的时间复杂度比Dijkstra算法高，但它能够处理更广泛的问题，包括检测负权回路。理解并掌握Bellman-Ford算法，对于学习更高级的图论和网络路由算法非常有帮助。

2024-03-24发表2024-08-24更新studynotes7 分钟读完 (大约976个字)

Dijkstra-学习笔记

Dijkstra算法是一种用于寻找图中两点之间最短路径的算法。它由荷兰计算机科学家艾兹赫尔·戴克斯特拉（Edsger W. Dijkstra）在1956年提出，并于1959年发表。

算法原理

Dijkstra算法适用于带权重的图，包括有向图和无向图。算法的核心思想是贪心法：每次找到距离起点最近的一个未被访问的顶点，然后考察所有由这个顶点引出的边，通过这个顶点更新起点到其他所有顶点的距离。

算法步骤

初始化：将所有顶点标记为未访问，设置起点到自身的最短距离为 \(0\)，到其他所有顶点的最短距离为无穷大。
选择最小距离的未访问顶点 \(u\)，访问并标记该顶点。
更新顶点 \(u\) 的邻接顶点的距离。
重复步骤2和3，直到所有顶点都被访问。

C++实现

下面是Dijkstra算法的一个基本C++实现示例：

#include <iostream>
#include <vector>
#include <limits>
#include <set>
using namespace std;
void Dijkstra(const vector<vector<pair<int, int>>>& graph, int src) {
	int V = graph.size();
	vector<int> dist(V, numeric_limits<int>::max());
	set<pair<int, int>> setds;
	dist[src] = 0;
	setds.insert(make_pair(0, src));
	while (!setds.empty()) {
		pair<int, int> tmp = (setds.begin());
		setds.erase(setds.begin());
		int u = tmp.second;
		for (auto i = graph[u].begin(); i != graph[u].end(); ++i) {
			int v = (i).first;
			int weight = (i).second;
			if (dist[v] > dist[u] + weight) {
				if (dist[v] != numeric_limits<int>::max()) {
					setds.erase(setds.find(make_pair(dist[v], v)));
				}
				dist[v] = dist[u] + weight;
				setds.insert(make_pair(dist[v], v));
			}
		}
	}
	cout << "Vertex Distance from Source\n";
	for (int i = 0; i < V; ++i) cout << i << "\t\t" << dist[i] << endl;
}
int main() { // 示例图的邻接表表示
	vector<vector<pair<int, int>>> graph = { {{1, 4}, {2, 1}}, {{2, 3}, {3, 2}, {4, 3}}, {{1, 1}, {3, 4}, {4, 5}}, {{4, 1}}, {} };
	Dijkstra(graph, 0);
	return 0;
}

注意事项

Dijkstra算法不能处理图中含有负权边的情况。如果图中含有负权边，可以考虑使用Bellman-Ford算法。
上述C++实现使用了std::set来寻找当前未访问顶点中距离最小的顶点，这使得算法的时间复杂度为 \(O(V^2)\)。对于稠密图来说是可接受的，但对于稀疏图，可以使用优先队列（如std::priority_queue）来优化，将时间复杂度降低到 \(O((V+E)log_2V)\)。

结论

Dijkstra算法是图论中一个非常基础且重要的算法，适用于解决许多实际问题，如网络路由、地图导航等。掌握其原理和实现于解决许多实际问题，如网络路由、地图导航等。掌握其原理和实现对于学习更高级的图论算法也非常有帮助。

扩展阅读

优化技巧：在实际应用中，Dijkstra算法的性能可以通过使用优先队列来大幅度提升。优先队列能够保证每次从队列中取出的都是当前最短距离的顶点，这样可以避免对所有顶点的遍历，从而降低算法的时间复杂度。
变体：Dijkstra算法有许多变体，例如，当需要找到从源点到所有其他顶点的最短路径时，可以稍微修改算法来实现。此外，对于特定类型的图（如非负权重图），Dijkstra算法尤其有效。
实际应用：在实际应用中，如地图软件的路径规划，通常会结合Dijkstra算法和其他技术（如A*搜索算法）来提高效率和准确性。

结语

Dijkstra算法是图论中的经典算法之一，它简洁而强大。通过本篇学习笔记，你应该对Dijkstra算法有了基本的了解和掌握。实际编程时，建议多做练习，尝试在不同的图结构上应用Dijkstra算法，以加深理解和熟练度。

2024-03-17发表2024-08-24更新studynotes7 分钟读完 (大约1075个字)

spfa学习笔记

引言

今天为了练链式前向星，写了一道橙题，然后看到 \(n \le 100\) 的数据量，毅然选择了使用SLF优化的SPFA求解（~~没错就是spfa~~。然而，前途是光明的，路途是坎坷的。折磨开始了……在历经4个小时的自学后，我学成归来解决了那道橙题，为了避免今天学了明天忘，记下这篇学习笔记。

2.算法详解

算法思想：我们用数组 \(d\) 记录每个结点的最短路径估计值，用邻接表来存储图 \(G\)。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点 \(u\) ，并且用u点当前的最短路径估计值对离开 \(u\) 点所指向的结点 \(v\) 进行松弛操作，如果 \(v\) 点的最短路径估计值有所调整，且 \(v\) 点不在当前的队列中，就将 \(v\) 点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

期望的时间复杂度 \(O(ke)\)，其中 \(k\) 为所有顶点进队的平均次数，可以证明 \(k\) 一般小于等于 \(2\)。

实现方法：

　　建立一个队列，初始时队列里只有起始点，再建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为 \(0\) 。然后执行松弛操作，用队列里有的点作为起始点去刷新到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。

关于优化：

SPFA(Shortest Path Faster Algorithm) [图的存储方式为邻接表]
是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。
算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。 直到队列为空时算法结束。
它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。
SPFA 在形式上和BFS非常类似，不同的是BFS中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。

判断有无负环：如果某个点进入队列的次数超过V次则存在负环（SPFA无法处理带负环的图）。

SLF 策略，设要加入的节点是 \(j\)，队首元素为 \(i\)，若 \(dist(j)<dist(i)\)，则将 \(j\) 插入队首，否则插入队尾。

例题&代码

洛谷P3905

没啥好讲解的，主要就是链式前向星存储图，邻接矩阵存储两点之间的路的好坏关系，然后在松弛边的时候若b[u][v]为false就用三目运算符返回w[i]，否则返回 \(0\)。（注意：道路是无权图，连边和存储好坏关系时正反存一次）

参考代码：

#include<iostream>
#include<cstring>
#include<cmath>
#include<deque>
using namespace std;
const int maxn = 107,inf=0x3f3f3f3f;
int idx;
bool vis[5*maxn];
int v[5*maxn],w[5*maxn],to[5*maxn],head[5*maxn],dis[5*maxn];
bool b[maxn][maxn];
void add(int u, int vi, int wi) {
	v[++idx]=vi;
	w[idx]=wi;
	to[idx]=head[u];
	head[u]=idx;
}
void spfa(int s,int n) {
	deque<int>q;
	memset(dis,inf,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[s]=0;
	q.push_back(s);
	vis[s]=1;
	while(!q.empty()) {
		int u=q.front();
		q.pop_front();
		vis[u]=0;
		for(int i=head[u]; i>-1; i=to[i]) {
			int vi=v[i];
			if(dis[vi]>dis[u]+(b[u][vi]?0:w[i])) {
				dis[vi]=dis[u]+(b[u][vi]?0:w[i]);
				if(!vis[vi]) {
					vis[vi]=1;
					if(!q.empty()&&dis[vi]<dis[q.front()])q.push_front(vi);
					else q.push_back(vi);
				}
			}
		}
	}
}
int main() {
	memset(head, -1, sizeof(head));
	memset(b, 1, sizeof(b));
	int n,m,d,A,B;
	cin >>n>>m;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}
	cin>>d;
	for(int i=0; i<d; i++) {
		int u , v;
		cin >> u >> v;
		b[u][v]=b[v][u]=0;
	}
	cin>>A>>B;
	spfa(A,n);
	cout<<dis[B]<<endl;
	return 0;
}

赶快学起来吧！

心得

唉，spfa你因太强而被处处针对，所以人还是要学会敛其锋芒啊！（~~spfa喜诈尸~~

2024-03-16发表2024-08-24更新studynotes6 分钟读完 (大约951个字)

链式前向星-学习笔记

存图的方式列举

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

存图方式的优劣对比

如果是稠密图的话，通常使用邻接矩阵，而稀疏图，大多使用邻接表。然而，邻接矩阵就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

样例输出 #1

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

Tarjan算法介绍

算法分析

伪代码

C++代码

1.切分定理

2. Kruskal算法

时间复杂度

核心伪代码

示例代码

3. Prim算法

时间复杂度

核心伪代码

示例代码

基本概念

构建AC自动机

构建Trie树

构建失败指针

搜索状态转移

总结

算法原理

算法步骤

C++实现

注意事项

扩展阅读

结语

算法原理

算法步骤

C++实现

注意事项

结论

扩展阅读

结语

目录

引言

2.算法详解

例题&代码

心得

目录

存图的方式列举

存图方式的优劣对比

为什么要用链式前向星

如何写链式前向星

例题

道路重建 洛谷P3905

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

链接

分类

最新文章

归档

标签

Your browser is out-of-date!

道路重建洛谷P3905