DAG上关键路径（超哥讲给张朴凡）
第一：什么是"DAG"
DAG意思是有向无环图，所谓有向无环图是指任意一条边有方向，
且不存在环路的图。第二：什么是“关键路径”
简单的将就是不可以推辞的活动组成的路径，
这对于工程上有着极其重要的应用，利用关键路径算法可以
计算那些事件是不可推辞的，必须如期完成。然后下面的是两种实现方法：
1. 究竟如何实现呢：
No.1：
通过拓扑排序，我们可以将DAG按照一定顺序排序，
这样DAG有了一定顺序，下面是个例子： No.2：
可以根据上述的“第二”，得出，“不可推辞”到底要求啥
是指————最长路径，对吧。（想一想，为什么，在向下看）
图： 所有事都必须做，那么它的关键路径是谁呢？
编号【圆圈上的】 2->3->6>(9或10)；
因为当这条都做到，就全做完了，然后想要缩短工程时间缩短它
就好了。
No.3：dp方程
每到一个点判断哪条路选择后，是最大的
即： 它要走的道=Max（它走的这条，它走的那条）；
Code：#include<bits/stdc++.h>
#define maxn 2001
using namespace std;
int a[10],head[maxn],n,p,f[maxn],tp[maxn],de[maxn],ds[maxn];
struct ss
{
int to,w,last;
}x[maxn*1000];
void add(int a,int b,int c)
{
x[++p].to=b;
x[p].last=head[a];
x[p].w=c;
head[a]=p;
}
int dp(int a)
{
if(f[a]!=0) return f[a];
if(!de[a]) return 0;
int v=head[a],t=0;
while(v)
{
if(dp(x[v].to)+x[v].w>t)
{
t=dp(x[v].to)+x[v].w;
ds[a]=x[v].to;
}
v=x[v].last;
}
f[a]=t;
return f[a];
}
void out(int a)
{
if(!a) return;
out(ds[a]);
printf("%d ",a);
}
int main()
{
scanf("%d",&n);
int a1,a2,a3;
while(scanf("%d%d%d",&a1,&a2,&a3)==3)
{
add(a2,a1,a3);
de[a2]++;
}
int ans=0,ansv;
for(int i=1;i<=n;i++)
if(dp(i)>ans)
{
ans=dp(i);
ansv=i;
}
printf("%d\n",ans);
out(ansv);
return 0;
}现在我们来思考一个问题，我如果有许多条关键路径那用什么方法可以全部输出呢？
所以引出下一个方法（我也不知道这个叫什么）：
先引出两个概念：
1.最早发生时间：意思事做这件事的最早时间，下面详细解释
首先，我们通过拓扑排序划分了阶段；所以下一阶段的某一件事要发生，
必须保证它的前面的事都完成了（即住进家前必须要买WIFI）；
那若有两件事哩，那么就是所有事都得完成（讲一下，住进家前除了要买
WIFI，还有要买家具，而且它们都得完成。所以要等它们都完成。）
那么最早发生就是前面最晚完成的完成了即就是上面的dp求的。
2.最晚发生时间：因为每件事情的需要时间不同，有的晚有的早，那么我用
时短的事晚发生一会，和用时长的一起结束也不会有任何影响，对吧。
就好像（我五分钟就能写完作业，你用60分钟，那我先玩55分钟，然后在
写，也是和你一起写完的作业）Code：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxm = 20;
const int maxn = 100;
const int inf = 0x3f3f3f3f;
struct node {
int x, y, w;
int next;
};
node edge[maxm];
int n, m;
int head[maxn];
//e代表活动开始的最早时间, l活动最迟开始的时间, ve[i]事件最早发生的时间, vl[i]事件最迟发生的时间 ,indegree[i]顶点的入度
//这个地方没必要分别为e，l开数组了，因为最后只是进行赋值，然后比较两个数是否相等而已，没必要开数组了就，不明白可以看下面的代码
int e, l, ve[maxn], vl[maxn], indegree[maxn];
stack<int> s, t; //s代表逆序的拓扑排序 ，t代表入度为零的栈，里面存放入度为零的点
int TopologicalSort() {
int i, cnt = 0;
for(i=1; i<=n; ++i) //入度为零的点入栈
if(!indegree[i]) {
t.push(i);
++cnt;
//printf("%d ", i);
}
while(!t.empty()) {
int a = t.top();
s.push(a);
//printf("%d ", a);
t.pop();
//去掉与入度为零的点的相连的边，对应的终点的入度减一
int k = head[a];
while(k != -1) {
if(!--indegree[edge[k].y]) {//终点的度减一后，如果度为零，入栈
t.push(edge[k].y);
++cnt;
//printf("%d ", edge[k].y);
}
if(ve[edge[k].y] < ve[a] + edge[k].w) //正拓扑排序求事件发生的最早时间ve[i]，到edge[k].y的最长路径
ve[edge[k].y] = ve[a] + edge[k].w;
k = edge[k].next;
}
}
if(cnt < n)
return 0;
return 1;
}
int main()
{
int i;
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
//建立邻接表
for(i=1; i<=m; ++i) {
scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].w);
++indegree[edge[i].y]; //终点的入度加一
edge[i].next = head[edge[i].x];
head[edge[i].x] = i;
}
if(TopologicalSort() == 0) { //在 TopologicalSort()函数里面已经解决了ve的问题
printf("不存在关键路径,存在环\n");
return 0;
}
memset(vl, inf, sizeof(vl));
vl[n] = ve[n]; //最后一个事件的最迟发生事件就等于最早发生时间，因为是最后一件事，也就是说这个工程干完了，以后就没有事情做了
while(!s.empty()) { //逆拓扑排序求vl[i]
int a = s.top();
s.pop();
int k = head[a];
while(k != -1) {
if(vl[a] > vl[edge[k].y] - edge[k].w) {
vl[a] = vl[edge[k].y] - edge[k].w;
}
k = edge[k].next;
}
}
printf("\n关键活动(该活动不能推迟开工)有:\n");
for(i=1; i<=n; ++i) {
int k = head[i];
while(k != -1) {
e = ve[i]; //该条边的起点代表事情，该条边表示的活动的最早发生时间就等于起点代表的事情的最早发生时间
//活动的最迟发生时间
l = vl[edge[k].y] - edge[k].w;
if(l == e)
printf("%d %d %d\n", i, edge[k].y, edge[k].w);
k = edge[k].next;
}
}
return 0;
}
然后，问一个问题：为什么当最晚发生时间==最早发生时间，它就一定是关键路径上的节点，急需证明，如果有大佬会，请私信我。