用php做的网站必备那些文件,易语言 网站开发,长春网站建设报价,制作俄语网站文章目录 12.图(下)(4).生成树和最小生成树#1.什么是生成树和最小生成树#xff1f;i.生成树ii.最小生成树 #2.Prim算法i.算法思想ii.看看例子iii.代码实现 #3.Kruskal算法i.算法思想ii.看看例子iii.代码实现 #4.次小生成树 (5).最短路径问题#1.加权有向图的最短路径问题#2.单… 文章目录 12.图(下)(4).生成树和最小生成树#1.什么是生成树和最小生成树i.生成树ii.最小生成树 #2.Prim算法i.算法思想ii.看看例子iii.代码实现 #3.Kruskal算法i.算法思想ii.看看例子iii.代码实现 #4.次小生成树 (5).最短路径问题#1.加权有向图的最短路径问题#2.单源最短路径问题—Dijkstra算法i.基本实现方法ii.优先队列优化方法 #3.多源最短路径问题—Floyd算法i.实现方法ii.求传递闭包 #4.还有更多 (6).拓扑排序#1.什么是拓扑序列#2.拓扑排序实现方式#3.关键路径和AOE网络i.什么是AOE网络ii.关键路径iii.代码实现 小结 12.图(下)
(4).生成树和最小生成树
#1.什么是生成树和最小生成树
i.生成树 G是一个连通无向图若G’是包含G中所有顶点的一个无回路的连通子图则称G’为G的一棵生成树其实还比较简单 生成树实际上就是某一张图的一种遍历结果它保证了生成的子图一定是一棵树因此对于一个具有n个顶点的无向图G其生成树G’一定恰好有n-1条边在生成树G’中任意添加一条边则会形成一个回路 通过DFS得到的生成树叫做深度优先生成树而BFS得到的生成树则叫做广度优先生成树连通无向图的生成树不是唯一的例如对于这个图 它的以1为起点的深度优先生成树如下 不过即便是限定了以1为起点这个无向连通图的深度优先生成树仍然不是唯一的例如我们很明显可以看到1→4→2→5→8也是一条合法的深度优先搜索路径这里只是举出了一种例子而以1为起点的广度优先搜索树如下 如果我们认为生成树是无序树那么以某个点为起点的广度优先生成树是唯一的
ii.最小生成树 如果我们给图的每条边赋上权重那么这个图就变成了有权无向图这时候我们希望求出一个生成树使得其所有路径的权重和最小这就是最小生成树(Minimum Spanning Tree, MST)也叫作最小代价生成树 这个问题其实不难解因为点到点之间只有连通的情况下才能走所以这个时候我们可以用一个贪心的思路来解决问题例如每次选取最小的边再在后续依次合并我们有两个比较经典的求最小生成树的方法分别是从一点开始慢慢成长成一棵大树的Prim算法不断取最小形成森林再逐渐合并形成一棵大树的Kruskal算法
#2.Prim算法
i.算法思想 带权连通无向图G(V,E)设U为V中构成最小生成树的顶点集合初始时 U { u 0 } U\{u_0\} U{u0}算法的流程如下
从G的某一顶点 u 0 u_0 u0出发选择与它关联的具有最小权值的边 ( u 0 , v ) (u_0,v) (u0,v)将其顶点加入集合 U U U中以后每一步从一个顶点在U中而另一个顶点不再U中的各条边选择权值最小的边(u, v)把它的顶点加入到集合U中直到UV为止
ii.看看例子 好像听懂了又好像没听懂我们来看看这个例子 在这里我们以1作为起始结点这时候 U { 1 } U\{1\} U{1}我们选择最短路径1和对应的顶点加入U则选择3加入U此时 U { 1 , 3 } U\{1,3\} U{1,3} 这时候再选择1和3能选到的最小权边这里选择4将顶点6放入 再选择最小的边(4, 2)此时将顶点4放入 U { 1 , 3 , 6 , 4 } U\{1, 3, 6, 4\} U{1,3,6,4} 然后选取最短的能够增加连接性的边(2, 5)此时将顶点2放入 U { 1 , 2 , 4 , 5 , 6 } U\{1, 2, 4, 5, 6\} U{1,2,4,5,6} 最后把最后一条边权为3的边放入U此时得到 U { 1 , 2 , 3 , 4 , 5 , 6 } U\{1,2,3,4,5,6\} U{1,2,3,4,5,6} 此时最小生成树已经生成完毕所以此时我们会发现实际上树的性质保证了从任何一个结点开始这个结构仍然是一棵树所以Prim算法可以随便从任何一个结点开始取到最后都能生成同一棵最小生成树
iii.代码实现 下面给出的是一个基于邻接表的利用优先队列优化的Prim算法
#include cstring
#include iostream
#include queue
using namespace std;
const int N 5050, M 2e5 10;struct E
{int v, w, x;
} e[M * 2];int n, m, h[N], cnte;void adde(int u, int v, int w)
{e[cnte] E{v, w, h[u]};h[u] cnte;
}struct S
{int u, d;bool operator(const S s1) const{return d s1.d;}
};priority_queueS q;
int dis[N];
bool vis[N];int res 0, cnt 0;void Prim()
{memset(dis, 0x3f, sizeof(dis));dis[1] 0;q.push({1, 0});while (!q.empty()) {if (cnt n) break;int u q.top().u, d q.top().d;q.pop();if (vis[u]) continue;vis[u] 1;cnt;res d;for (int i h[u]; i; i e[i].x) {int v e[i].v, w e[i].w;if (w dis[v]) {dis[v] w, q.push({v, w});}}}
}int main()
{cin n m;for (int i 1, u, v, w; i m; i) {cin u v w;adde(u, v, w);adde(v, u, w);}Prim();if (cnt n)cout res;elsecout No MST.;return 0;
}你可以试着理解一下优化后的版本下面是一个对于邻接矩阵的版本
void prim(int cost[][MAXN], int n, int u)
{int lowcost[MAXN], min;int closest[MAXN];int i, j, k;for (i 1; i n; i) {lowcost[i] cost[u][i];closest[i] u;}for (i 1; i n; i) {min MAXINT;for (j 1; j n; j) {if (lowcost[j] ! 0 lowcost[j] min) {min lowcost[j];k j;}printf({%3d%3d%3d%5d} , closest[k], k, min);lowcost[k] 0;for (j 1; j n; j) {if (cost[k][j] ! 0 cost[k][j] lowcost[j]) {lowcost[j] cost[k][j];closest[j] k;}}}}
}#3.Kruskal算法
i.算法思想 Kruskal算法的思想更加直观一点
初始时 T ( V , Φ ) T(V,\Phi) T(V,Φ)即T由n个连通分量组成每个连通分量只有一个顶点没有边把边的权值按照从小到大排序依次进行如下选择若当前被选择的边的两个顶点在不同的连通分量中则把这条边加到T中即每次选权最小且不构成回路的一条边加入T直到T中有n-1条边为止 Kruskal的过程强烈依靠并查集来实现它会判断候选边的两个顶点是否在不同的集合如果在同一个集合放弃这条边否则就选择这条边同时合并两个集合
ii.看看例子 首先选取最小的一条边1 然后再选取最小的一条边2 之后再选择3 再选择最小的一条边4 这一次需要从所有边权为5的边中选一条只有(2, 3, 5)这条边满足两个顶点在不同的集合中因此我们选取这一条至此整个最小生成树就生成完毕了
iii.代码实现
#include iostream
#include queue
#include vector
#include algorithm
using namespace std;
constexpr int eN 2e550; // 边
constexpr int nN 5e320; // 点struct edge
{int beg;int end;int w;bool operator(const edge e) const{return w e.w;}
};edge g[eN];
vectorint v(nN, -1);
int mst{ 0 };int Find(vectorint vec, int x)
{if (vec[x] 0) return x;return Find(vec, vec[x]);
}void Union(vectorint vec, int x, int y)
{int px{ Find(vec, x) }, py{ Find(vec, y) };if (px ! py) {vec[px] vec[py];vec[py] px;}
}void Kruskal(int N, int M)
{sort(g 1, g 1 M);for (int i 1; i M; i) {int px{ Find(v, g[i].beg) }, py{ Find(v, g[i].end) };if (px ! py) {Union(v, px, py);mst g[i].w;}}
}int main()
{int N{ 0 }, M{ 0 };cin N M;for (int i 1; i M; i) {int st{ 0 }, end{ 0 }, w{ 0 };cin st end w;g[i] { st, end, w };}Kruskal(N, M);int root{ Find(v, 1) };for (int i 2; i N; i) {if (Find(v, i) ! root) {mst -1;break;}}cout mst endl;return 0;
}简单的算法对吧
#4.次小生成树 次小生成树采取了一个试探的方式对于当前已经生成的最小生成树去尝试换用别的边
#include iostream
#include algorithm
using namespace std;constexpr int INF 0x3f3f3f3f;
constexpr int N 505;
int G[N][N]{ {0} }, used[N][N]{ {0} }, path[N][N]{ {0} };
int pre[N]{ 0 }, dis[N]{ 0 };
bool vis[N]{ false };
int m, n;void init()
{for (int i 1; i n; i) {vis[i] false;for (int j 1; j n; j)G[i][j] INF;}
}int Prim(int st)
{int sum 0, Min;for (int i 1; i n; i) {dis[i] G[st][i];pre[i] st;}dis[st] 0;vis[st] 1;for (int i 1; i n; i) {Min INF;for (int j 1; j n; j) {if (!vis[j] Min dis[j]) {Min dis[j];st j;}}vis[st] 1;sum Min;used[st][pre[st]] used[pre[st]][st] 1;for (int j 1; j n; j) {if (vis[j] j ! st)path[j][st] path[st][j] max(path[j][pre[st]], dis[st]);if (!vis[j] dis[j] G[st][j]) {dis[j] G[st][j];pre[j] st;}}}return sum;
}int sec_Prim(int tmp)
{int sum{ INF };for (int i 1; i n; i) {for (int j 1; j n; j) {if (i ! j !used[i][j])sum min(sum, tmp G[i][j] - path[i][j]);}}return sum;
}通过这个方式可以在连通的情况下求出另外一个最小生成树这个次小生成树可能比最小生成树更大也可能和当前的最小生成树相同
(5).最短路径问题
#1.加权有向图的最短路径问题 从学校出发到最近的餐厅要走多少路呢作为一个懒人我肯定会选择走更短的路所以我们可以把这个问题抽象一下把地图上的每个地标作为顶点选择两个地标间的最短路径长度为对应的边权重于是求到更加远的不能直达的两点的最短路径就是我们希望解决的问题了而这也就是加权有向图的最短路径问题对于一个无向图其实事情也是一样的我们可以认为它是一个A到B和B到A的边权相同的图
#2.单源最短路径问题—Dijkstra算法 Dijkstra是个很厉害的人从他的名字就可以看出来他的名字里居然同时有i,j,k三个连续字母 Dijkstra算法用于求单源无负权边图的最短路径也就是求得从一个点开始到全局所有其他点的最短路径但是要注意的是Dijkstra不能应对负权边的问题这个问题在Bellman-Ford算法有了解决
i.基本实现方法 Dijkstra的算法是这样的
设 S { v } S\{v\} S{v}即从顶点v出发按以下步骤逐个求得从v到其他顶点的最短路径直到把所有顶点的最短路径求出 a. 选取不在S中且具有最小距离的顶点Kb.把K加入集合Sc.修改不再S中的顶点的距离 我们需要使用三个数组来存放有向图的各种信息
dist[]: 记录各个顶点的当前距离(当前到达v的距离)pre[]: 存放从起点v到顶点j的最短路径j前面的顶点S[]: 类似于visited即标记已经求出最短路的顶点 例如对于下面这张图 我们根据算法的具体操作每一步可以得到dist,pre,S三个数组的变化如下 具体的步骤这里就不再赘述了接下来给出一段基本的实现思路
int cost[MAXN][MAXN]{{0}};
int dist[MAXN]{0}, pre[MAXN]{0}, n{0}, v{0};void dijkstra(int n, int v)
{bool s[MAXN]{0};int i, j, k, min;for (i 1; i n; i) {dist[i] cost[v][i];s[i] 0;if (dist[i] MAXINT) pre[i] v;else pre[i] 0;}s[v] true;pre[v] 0;for (i 1; i n; i) {min MAXINT;k 0;for (j 1; j n; j) {if (!s[j]) if (dist[j] ! 0 dist[j] min) {min dist[j];k j;} }if (k 0) break;s[k] 1;for (j 1; j n; j) {if (s[j] 0 cost[k][j] MAXINT) {if (dist[k] cost[k][j] dist[j]) {dist[j] dist[k] cost[k][j];pre[j] k;}}}}
}这样的实现方法的时间复杂度为 O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)
ii.优先队列优化方法 我们可以基于优先队列的方式来优化Dijkstra
constexpr int maxn 5e5 20;struct edge
{int v, w;
};struct node
{int dis, u;bool operator(const node a) const{return dis a.dis;}
};vectoredge e[maxn];
int dis[maxn], vis[maxn];
priority_queuenode, vectornode, greaternode q;void dijkstra(int n, int s)
{memset(dis, 0x3f, sizeof(dis));dis[s] 0;q.push({ 0, s });while (!q.empty()) {int u q.top().u;q.pop();if (vis[u]) continue;vis[u] 1;for (const auto ed : e[u]) {int v ed.v, w ed.w;if (dis[v] dis[u] w) {dis[v] dis[u] w;q.push({ dis[v], v });}}}
}这种情况下时间复杂度可以被优化到 O ( ∣ E ∣ log ∣ V ∣ ) O(|E|\log|V|) O(∣E∣log∣V∣)
#3.多源最短路径问题—Floyd算法 Floyd比较好的一点是可以直接求出每一个点到其他的点的最短路径长度比较坏的一点是它的时间复杂度非常高为 O ( ∣ V ∣ 3 ) O(|V|^3) O(∣V∣3)对于一个数据量非常大的图我们可能得换用Johnson算法求出全局的最短路径
i.实现方法 Floyd的思路是这样的假设求从 v i v_i vi到 v j v_j vj的最短路径如果 v i v_i vi到 v j v_j vj有边那就存在一条长度为cost[i][j]的边但这不一定是最短路径因为可能存在一条从 v i v_i vi到 v j v_j vj但包含其他中间点的更短的路径 因此我们需要进行n次试探测试看从 v i v_i vi到 v j v_j vj是否能有包含其他中间点的更短路径所以Floyd的基于代价矩阵A实现对于第k步的 A ( k ) A^{(k)} A(k)我们可以有以下递推公式 { A ( 0 ) ( i , j ) c o s t ( i , j ) , A ( k ) ( i , j ) min { A ( k − 1 ) ( i , j ) , A ( k − 1 ) ( i , k ) A ( k − 1 ) ( k , j ) } , 1 ≤ k ≤ n \begin{cases} A^{(0)}(i,j) cost(i,j),\\ A^{(k)}(i,j) \min\{A^{(k-1)}(i,j), A^{(k-1)(i,k)A^{(k-1)}(k,j)}\}, 1\leq k\leq n \end{cases} {A(0)(i,j)cost(i,j),A(k)(i,j)min{A(k−1)(i,j),A(k−1)(i,k)A(k−1)(k,j)},1≤k≤n A ( 0 ) A^{(0)} A(0)为初始给定的代价矩阵而 A ( k ) ( i , j ) ( 1 ≤ i , j ≤ n ) A^{(k)}(i,j)(1\leq i, j\leq n) A(k)(i,j)(1≤i,j≤n)表示从顶点i到顶点j的中间顶点序号不大于k的最短路径长度 有了这个我们就可以递推地产生 A ( 0 ) , A ( 1 ) , . . . , A ( n ) A^{(0)},A^{(1)}, ..., A^{(n)} A(0),A(1),...,A(n)了 A ( n ) A^{(n)} A(n)是我们最后需要的解所以它的代码真的超级简单
void floyd(int n)
{for (int i 1; i n; i) {for (int j 1; j n; j) {a[i][j] cost[i][j];path[i][j] 0; // path数组用于存储路径}}for (int k 1; k n; k) {for (int i 1; i n; i) {for (int j 1; j n; j) {if (a[i][j] a[i][k] a[k][j]) {a[i][j] a[i][k] a[k][j];path[i][j] k;}}}}
}一个非常简单的三重循环一个直接就能看出来的 O ( n 3 ) O(n^3) O(n3)时间复杂度对吧
ii.求传递闭包 对于一个关系R具备某个性质P的闭包可以定义为能够使关系R满足属性P的最小集合关系R可能本身不满足P我们可以添加较少的一些元组使得其满足性质P而传递闭包需要的则是 x R y , y R z ⇒ x R z xRy, yRz\Rightarrow xRz xRy,yRz⇒xRz R的传递闭包记为t®它可以用这个算法得到 t ( R ) ⋃ i 1 ∞ R i t(R) \bigcup_{i1}^\infty R^i t(R)i1⋃∞Ri 对于一个有限的关系R我们可以用有限次的并完成这个操作因此我们可以用Floyd算法求传递闭包
...
for (int k 1; k n; k) {for (int i 1; i n; i) {for (int j 1; j n; j) {a[i][j] | a[i][k] a[k][j];}}
}#4.还有更多 实际上求最短路径的方法还有很多例如Johnson全源最短路算法、Bellman-Ford算法等等其中Bellman-Ford算法在后续的 《计算机网络》 课程中还会学到(基于距离向量的路由算法)你可以去了解一下OI-Wiki就是一个很不错的选择
(6).拓扑排序
#1.什么是拓扑序列 例如计算机科学与技术学院开的很多课具有先修课程的要求
课程代号课程名称先修课C1程序设计基础无C2离散数学C1C3数据结构C1,C2C4汇编语言C1C5语言的设计与分析C3,C4C6计算机原理C10C7编译原理C3,C5C8操作系统C3,C6C9高等数学无C10普通物理C9 如果以顶点作为活动我们可以得到以下的有向图 这样的图被我们称为顶点表示活动的网络简称AOV网络所以我们需要一个顺序能够在先修的限制下得到一个合法的课程修读顺序 接下来是一大堆定义设S是一个集合R是S上的一个关系a,b是S中的元素若 ( a , b ) ∈ R (a,b)\in R (a,b)∈R则称a是b关于R的前驱元素b是a关于R的后继元素 设S是一个集合R是S上的一个关系a,b,c是S中的元素若有 ( a , b ) ∈ R (a,b)\in R (a,b)∈R和 ( b , c ) ∈ R (b,c)\in R (b,c)∈R则必有 ( a , c ) ∈ R (a,c)\in R (a,c)∈R则称R是S上的传递关系 若对于S中的任意元素不存在 ( a , a ) ∈ R (a,a)\in R (a,a)∈R则称R是S上的一个非自反关系 若S上的一个关系R是传递的以及非自反的则称R是S上的一个半序关系 在任何一个具有半序关系R的有限集合中至少有一个元素没有前驱也至少有一个元素没有后继 若R是集合S上的一个半序关系 A a 1 , a 2 , . . . , a n Aa_1,a_2,...,a_n Aa1,a2,...,an是S中元素的一个序列且当 ( a i , a j ) ∈ R (a_i,a_j)\in R (ai,aj)∈R时有 i j ij ij则称A是相对于R的一个拓扑序列若 a i a_i ai和 a j a_j aj关于R没有关系则它们在A中的排列次序不受限制 所以在这么多定义之后我们就知道什么是拓扑序列了实际上就是希望得到一个AOV网络的合法执行顺序所以很容易知道AOV网络中不能存在有向环路否则不可能得出一个能够合法执行的顺序而操作一个有向图得到拓扑序列的过程就是拓扑排序
#2.拓扑排序实现方式 其实拓扑排序实现起来非常简单
在网络中选择一个没有前驱的顶点输出从网络中删除该顶点和以它为尾的所有有向边 之后重复这两个步骤直到所有的顶点都被输出或网络上的顶点都有前驱顶点(出现回路) 为止 在计算机中的拓扑排序我们利用邻接表存储有向图并且维护一个储存每个顶点入度的数组当某个顶点的入度为0时就输出这个顶点同时将该顶点的所有后继顶点入度减一为了避免重复检测入度为0的顶点我们可以用一个队列/栈存放这些度为0的顶点在这里我们采取队列实现
#include iostream
#include queue
#include vector
using namespace std;
constexpr int MAXN 5e5 20;int n, m;
vectorint G[MAXN];
int in[MAXN]{ 0 }; // 存储每个结点的入度bool toposort()
{vectorint L;queueint S;for (int i 1; i n; i)if (in[i] 0) S.push(i);while (!S.empty()) {int u S.front();S.pop();L.push_back(u);for (const auto v : G[u]) {if (--in[v] 0) {S.push(v);}}}if (L.size() n) {for (const auto i : L) cout i ;return true;}else {return false;}
}int main()
{cin n;for (int i 1; i n; i) {int in1{ 0 };do {cin in1;if (in1 ! 0) {G[i].push_back(in1);in[in1];}} while (in1 ! 0);}toposort();return 0;
}这个过程非常简单我们首先从邻接表中找出入度为0的顶点加入队列后依次取出把与它相连的入度为0的顶点都入队然后把它加入输出序列中一直这么操作直到队列为空为止这时候如果输出序列和顶点数相同则无环拓扑排序正常否则其中存在环无法进行拓扑排序
#3.关键路径和AOE网络
i.什么是AOE网络 接下来是最后一个问题如果我们把顶点作为某个状态而有向边代表活动则会得到另一种网络AOE网络(Activity On Edge Network) 表示实际工程的AOE-网络应该没有有向回路存在唯一的入度为0的开始顶点唯一的出度为0的结束顶点 例如下面这个AOE网络其中V1表示工程开始V2表示活动a1完成V3表示活动a2完成V4表示活动a3和a4完成V5表示活动a5和a6完成此时整个工程就完成了
ii.关键路径 在AOE网络中我们主要关心完成整个工程至少需要多少时间这个问题其实比较好解决因为完成整个工程的最小时间是从开始顶点到结束顶点的最长路径长度 而我们称从开始顶点到结束顶点的最长路径为关键路径一个AOE网络可以有多条关键路径关键路径上的所有活动都是关键活动 例如我们在上图中用到的这个AOE网络我们可以定义最早开始时间例如V1作为起点肯定是0而V2只依赖从V1开始完成活动a1所以V2最早也要从5才能开始对应的我们可以得出V3为7而V4要好好考虑一下因为V4同时依赖于V2和V3从V2到V4需要到8而从V3到V4需要13因此这时候我们会发现因为V4依赖于V3而V3到V4最早也要在13才能达到所以V4的最早开始时间是13对应的也可以得到V5的最早开始时间是17 有最早开始时间就可以有最晚开始时间因为我们刚刚发现这个AOE网络中有那么几个活动因为另外的活动影响中间存在一段时间什么都不用干这时候我们要倒着推某个事件的最迟开始时间为所有事件的完成时间减去从当前事件到事件完成顶点的最长路径长度因此我们可以知道V5的最迟开始时间是17V4的最迟开始时间是13V3的最迟开始时间是17-max{10, 3}7V2的最迟开始时间是10V1当然是0啦 你会发现V2的最迟开始时间是10最早开始时间是5这也就意味着对应V2的活动并没有那么急迫换而言之V2对应的活动并不是影响整个工程结束的关键活动 对于活动我们同样可以定义活动的最早开始时间和最迟开始时间对于活动 a i a_i ai它由边 j , k j,k j,k表示则最早开始时间就是顶点j的最早开始时间而最迟开始时间则是顶点k的最迟开始时间减去活动 a i a_i ai的时间这样一来我们就可以求得对应各个活动的最早开始时间和最迟开始时间 我们称最迟开始时间等于最早开始时间的活动为关键活动所以在求解关键活动的时候我们需要求到整个AOE网络的四个数组顶点最早开始时间顶点最迟开始时间活动最早开始时间活动最迟开始时间下面我会给出一段代码解决这个问题
iii.代码实现 这里用用一道题作为例子: 参考代码如下
#include iostream
#include vector
#include queue
#include map
#include cstring
#include algorithm
using namespace std;
constexpr int MAXN 120;struct edge
{int beg;int end;int w;
};vectoredge e[MAXN];
int in[MAXN]{ 0 };
int ee[MAXN]{ 0 }, le[MAXN]{ 0 };
int xe[MAXN]{ 0 }, l[MAXN]{ 0 };
bool v[MAXN]{ 0 };
vectoredge all_es;
mapint, edge ma;
vectorint ans;bool toposort(int n)
{vectorint L;queueint S;for (int i 1; i n; i) {if (in[i] 0) S.push(i);}while (!S.empty()) {int u{ S.front() };S.pop();if (v[u]) continue;v[u] true;L.push_back(u);for (const auto v : e[u]) {if (--in[v.end] 0) S.push(v.end);ee[v.end] max(ee[v.end], ee[u] v.w);}}if (L.size() n) {ans L;return true;}else {ans vectorint{};return false;}
}int main()
{int n{ 0 }, m{ 0 };cin n m;memset(le, 0x3f, sizeof(le));all_es.push_back({ 0,0,0 });ee[1] 0, le[n] n;for (int i 1; i m; i) {int u, v, w;cin u v w;e[u].push_back({ u, v, w });all_es.push_back({ u,v,w });in[v];}bool available{ toposort(n) };if (available) {int mx 0, mxi 0;for (int i 1; i n; i) {if (ee[i] mx) {mx ee[i];mxi i;}}le[mxi] ee[mxi];for (auto it ans.rbegin() 1; it ! ans.rend(); it) {for (const auto eg : e[*it]) {le[*it] min(le[*it], le[eg.end] - eg.w);}}for (int i 1; i m; i) {xe[i] ee[all_es[i].beg];l[i] le[all_es[i].end] - all_es[i].w;}vectoredge all;mx 0;for (int i 1; i n; i) {mx max(mx, ee[i]);}cout mx endl;for (int i 1; i m; i) {if (xe[i] l[i]) {all.push_back(all_es[i]);}}stable_sort(all.begin(), all.end(),[](const edge e1, const edge e2) {if (e1.beg ! e2.beg) {return e1.beg e2.beg;}else {return e1.end e2.end;}});for (const auto fe : all) {cout fe.beg - fe.end endl;}}else cout 0 endl;return 0;
}小结 图论始终是古老而又富有活力的学科我们在这一篇中只是简单地介绍了一系列关于图的算法和数据结构还有很多很多关于图的内容限于篇幅我没有在这里介绍在未来有可能会在这个系列中补充。 到这里数据结构这个系列的博客的所有课内部分就基本结束了在之后我会用几篇博客来单独补充红黑树、B树和B树等一系列在之前的博客中没有具体讨论的内容不过最近就要暂时停更了感谢大家一个学期以来的支持
