C/C++: 关键路径

????????关键路径在找最早发生时间的时候要正着找，找最晚发生时间的时候要找到最后一个终点的最早发生时间后，倒着减去每个边的权值，就是各点的最晚发生时间。

? ? ? ? 具体注释在文中。

/**
*
* Althor: Hacker Hao
* Create: 2023.12.13    /!ATTENTION!/
* Meaning: This article commemorates the Nanjing Massacre
*/
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 10;
int vexnum, arcnum;  //顶点个数和边的个数
int vet[MAX], vlt[MAX];  //各点的最早发生时间和最晚发生时间的集合

//注意，文章没有设置活动的最早、最晚时间。因为用点求出每个点的最早和最晚相同时便输出，利用循环
//把每个关键路径都在循环中输出

struct EdgeNode
{
	int adjvex;
	int value;
	EdgeNode* nextarc;
};

struct VexNode
{
	int indegree;
	int data;
	EdgeNode* firstarc;
};

VexNode Vex[MAX];   //顶点集合

/*
* eet:EdgeEarlyTime
* elt:EdgeLaterTime
* vet:VexEarlyTime
* vlt:VexLaterTime
*/

//在拓扑排序中，up利用了同一个for循环，顺便把各点的最早发生时间求出了
bool TopoSort(vector<int>& topo)
{
	stack<int> stack;
	for (int i = 0; i < vexnum; i++)
	{
		if (Vex[i].indegree == 0)
			stack.push(i);      //先把里面入度为0的进栈一下
	}

	while (!stack.empty())       //栈不能为空，否则就是结束了
	{
		int top = stack.top();
		stack.pop();
		topo.push_back(top);       //保存出栈的值到vector向量中
        

        //一定注意，这是在邻接表中遍历每个边（就是小链表的挨个遍历）
		for (EdgeNode* e = Vex[top].firstarc; e != NULL; e = e->nextarc)
		{
			int end = e->adjvex;
			Vex[end].indegree--;
			if (Vex[end].indegree == 0)
				stack.push(end);
			if (vet[top] + e->value > vet[end])
				vet[end] = vet[top] + e->value;
		}
	}

	if (topo.size() < vexnum)
		return false;       //存在环，不合适
	else
		return true;
}

void CriticalPath()        //关键路径
{
	vector<int> topo;
	TopoSort(topo);

	for (int i = 1; i <= vexnum; i++)
		vlt[i] = vet[vexnum];

	//倒过来求各点的vlt
	for (int i = topo.size() - 1; i >= 0; i--)
	{
		int pre = topo[i];
		for (EdgeNode* e = Vex[pre].firstarc; e != NULL; e = e->nextarc)
		{
			int end = e->adjvex;
			if (vlt[end] - e->value < vlt[pre])  //倒着从终点求vlt
				vlt[pre] = vlt[end] - e->value;
		}
	}

	//通过vet和vlt求eet和elt
	cout << "以下为关键路径: " << endl;
	for (int i = 1; i <= vexnum; i++)
	{
		for (EdgeNode* e = Vex[i].firstarc; e != NULL; e = e->nextarc)
		{
			int end = e->adjvex;
			int eet = vet[i];
			int elt = vlt[end] - e->value;
			if (eet == elt)
				cout << "v" << i << "->" << "v" << end << ", " << e->value << endl;

		}
	}

}

int main()
{
	cout << "请输入顶点数和边数：" << endl;
	cin >> vexnum >> arcnum;
	cout << "请输入每个边依赖的两个顶点和权值：" << endl;
	for (int i = 0; i < arcnum; i++)
	{
		int x, y, z;
		cin >> x >> y >> z;    //出点，入点，权值
		Vex[y].indegree++;     //入点的入度++
		EdgeNode* e = new EdgeNode;

		e->adjvex = y;         //赋值
		e->value = z;

		e->nextarc = Vex[x].firstarc;
		Vex[x].firstarc = e;      //把e这个点加入到邻接表中

	}
	CriticalPath();   //关键路径函数
	return 0;

}

//输入：
6 8
1 2 3
1 3 2
3 4 4
4 6 2
2 5 3
2 4 2
3 6 3
5 6 1

输出：