暖树

图中的最短路径问题 Dijkstra算法 基本描述 主要用来解决单源最短路径问题，采用贪心策略，无法解决存在负权值的问题。 实现思路 首先设置一个集合SSS，用来存放已经确定最短路径的顶点；初始化图TTT； 将源点uuu加入集合SSS并初始化数组dis[i]表示源点到点iii的距离；初始化：dis[u]=0 dis[other]=MAX 然后从图TTT中选取一个与uuu直接相连权值最小的点vvv加入集合SSS； 对与vvv相邻的每个点xxx进行松弛操作：dis[x]=min(dis[x],dis[x]+G[v][x]) 重复3 4操作直至TTT为空； 示例代码 无优化 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071struct edge{ int to; int nextEdge; int w;} e[100010];int c ...

拓扑排序 概述 对一个DAGDAGDAG(有向无环图)GGG进行拓扑排序，是将GGG中所有顶点排成一个线性序列，使得图中任意一对顶点uuu和vvv，如果存在一条有向边u−>vu->vu−>v则uuu在vvv之前出现。简单来说，是在不破坏节点先后顺序的情况下，把DAGDAGDAG拉成一条链。 注意：拓扑排序可能不是唯一的。 Kahn算法 首先获取所有**入度为000**的节点，将他们排在前面然后从图中删除。此时有些点的入度会减少，重复前面的操作直到所有点都被删除(输出)。 我们可以通过BFSBFSBFS来实现，使用一个队列，首先遍历入度为0的节点(这些节点入队)，队首出队，与队首所连节点度数−1-1−1，如果有节点度数减为0将其加入队列，重复上述操作直至队列为空。 示例代码 1234567891011121314151617181920212223242526272829303132333435struct edge{ int to;//指向的节点 int NextE;//下一条边} e[100];int num_e = 0;//边数int hea ...

图的表示 邻接矩阵 使用graph[i][j]>0graph[i][j]>0graph[i][j]>0表示顶点iii与jjj之间存在一条边，graph[i][j]graph[i][j]graph[i][j]的值可以表示边的权值。 12345678910void getGraph(int n, int m){ for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; graph[u][v] = 1; //无向图graph[v][u] = 1; }} 邻接表 数组模拟 使用graph[i][0]graph[i][0]graph[i][0]表示和顶点iii相连的点有多少个，graph[i][j]graph[i][j]graph[i][j]表示第jjj个与iii相连的点的编号。例如graph[2][0]=5graph[2][0]=5graph[2][0]=5表示与222号顶点相连的点 ...

图DFS和BFS 题目描述 小 K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小 K 求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。 假设洛谷博客里面一共有 n(n≤105)n(n\le10^5)n(n≤105) 篇文章（编号为 1 到 nnn）以及 m(m≤106)m(m\le10^6)m(m≤106) 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章，请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。 这边是已经整理好的参考文献关系图，其中，文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。 请对这个图分别进行 DFS 和 BFS，并输出遍历结果。如果有很多篇文章可以参阅，请先看编号较小的那篇(因此你可能需要先排序)。 输入格式 共 m+1m+1m+1 行，第 1 行为 2 个数，nnn 和 mmm，分别表示一共有 n(n≤105)n(n\le10^5)n(n≤10 ...

E3-G Swamp 题目描述 Oh no! Q 被派到了一片沼泽做生态调查，他需要前往沼泽的 $n 个地点（编号为个地点（编号为个地点（编号为 1,2,…,n$ ），Q一开始在 1 号点。这 n 个地点中有 m 条边使它们联通。连接$ u,v $的边会经过深度为 hu,vh_{u,v}hu,v​ 的泥潭。有洁癖的 Q 想让他的鞋子尽可能干净，请你帮他算出从 1 号点开始走完剩下的 $(n−1) $个地点，Q 需要经过的最深泥潭的最小深度。 输入 第一个数为数据组数 t(5≤t≤15).t (5≤t≤15).t(5≤t≤15). 对于每组数据，每行2个整数n,m(1≤n≤2×105,1≤m≤4×105).n,m (1≤n≤2×10^5,1≤m≤4×10^5).n,m(1≤n≤2×105,1≤m≤4×105). 接下来m行，每行三个整数u,v,hu,v(1≤u,v≤n),hu,vu,v,h_{u,v} (1≤u,v≤n), h_{u,v}u,v,hu,v​(1≤u,v≤n),hu,v​ 在 int 范围内，代表地点 u 到地点 v 有一条通路，且需要经过深度为$ h_{u,v}$ 的泥潭 ...

并查集 定义 并查集是一种树形数据结构，用于处理一些不相交集合的合并，查询问题。 主要构成 一个数组pre[]pre[ ]pre[]，记录了每个点的前驱节点是谁； 两个函数：find(x)find(x)find(x)，用于查找指定节点属于哪个分支（集合）；join(x,y)join(x,y)join(x,y)，合并两个节点； 作用 求连通分支数（一个图中互不连通的连通子图数）； 意义 当我们判断两点是否连通时，可以往根部进行查找，只要两点可由相同的一点的分支下来那么两点就是连通的。 用集合中某个元素来代表这个集合，则该元素称为此集合的代表元。 实现 pre[] 我们用一个数组来记录每节点的前驱，比如pre[5]=6pre[5]=6pre[5]=6代表5号节点的前驱节点是6号节点。如果一个节点的前驱节点是它自己，则说明此节点为根节点。 find(x) 查找xxx所在分支的根节点，从xxx开始通过pre[x]pre[x]pre[x]获取它的前驱节点，重复获取直到抵达根节点。 12345678int find(int x){ while(pre[x]!=x) { ...