最近一直被概率论所虐，今天要交作业于是乎昨天急急忙忙的写完了，里面有个关于关键路径的东西，以前没有见过也感觉没啥用所以一直拖到现在才学。=-=拖延症啊。
什么叫关键路径。
在一个有向图中，如果用顶点表示事件，弧表示活动，弧上对应的权值表示活动持续的时间，那么称这个有向图为AOE网，常用于估算工程的完成时间。
(AOV网：在一个有向图中，如果以顶点表示活动，用顶点之间的关系来表示活动的先后关系，那么称此有向图为AOV网，用于分析工程各项子任务的完成先后顺序，即拓扑排序。）
关键路径为AOE网中从顶点到汇点路径长度最长的路径称为关键路径。
关键路径中主要有以下术语：
活动开始的最早时间e[i]
活动开始的最晚时间l[i]
事件开始的最早时间ve[i]
事件开始的最晚时间vl[i]
其中，关键活动就是找那些e[i]=l[i]的活动
为了求得e[i]和l[i]，首先应该知道事件的字早发生时间和最迟发生时间。如果活动ai由弧<i,j>表示，其持续时间为dut<i,j>,则有如下关系：
e[i]=ve[i]
l[i]=vl[k]-dut(<j,k>)
求解ve[j]和vl[j]需分两个步骤进行：
求拓扑序从前往后求ve,ve[j]=max(ve[i]+dut(<i,j>)
逆拓扑序从后往前求vl,vl[i]=min(vl[j]-dut(<i,j>)
其中，ve[0]=0,vl[n-1]=ve[n-1];
其实只要求一遍拓扑序，在求的时候得到ve然后利用已经生成的拓扑序求vl即可。
求关键路径的算法分析
（1） 求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；
（2） 只有缩短关键活动的工期才有可能缩短工期；
（3） 若一个关键活动不在所有的关键路径上，减少它并不能减少工期；
（4） 只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。
下面是实现代码：
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<iostream>
#include<cmath>
using namespace std;
#define maxn 1000
int head[maxn];
int cnt;
struct eg
{
int u,next;
int w;
}edge[maxn*maxn*2];
void add(int u,int v,int w)
{
edge[cnt].u=u;
edge[cnt].w=w;
edge[cnt].next=head[v];
head[v]=cnt++;
}
int n;
int ve[maxn];
int vl[maxn];
int ind[maxn];
stack<int> T;
void ini()
{
memset(head,-1,sizeof(head));
cnt=0;
while(!T.empty())T.pop();
memset(edge,0,sizeof(edge));
memset(ind,0,sizeof(ind));
memset(ve,0,sizeof(ve));
memset(vl,0,sizeof(vl));
}
void topo()
{
stack<int> s;
while(!s.empty())s.pop();
int cnt=0;
for(int i=0;i<n;i++)
if(ind[i]==0){
s.push(i);break;
}
while(!s.empty()){
int tmp=s.top();
T.push(tmp);
for(int k=head[tmp];~k;k=edge[k].next){
int i=edge[k].u;
if(--ind[i]==0)
s.push(i);
if(ve[tmp]+edge[k].w>ve[i])
ve[i]=edge[k].w+ve[tmp];
}
}
if(cnt<n){
printf("circle");
return;
}
}
void getCriticalPath()
{
topo();
while(!T.empty()){
int j=T.top();T.pop();
for(int p=head[j];~p;p=edge[p].next){
int k=edge[p].u;
if(vl[k]-edge[p].w<vl[j])
vl[j]=vl[k]-edge[p].w;
}
}
for(int i=0;i<n;i++){
for(int p=head[i];~p;p=edge[p].next){
int k=edge[p].u;
if(ve[k]==vl[k]-edge[p].w)
printf("%d %d %d\n",i,k,dege[p].w);
}
}
}
int main()
{
int m;
while(~scanf("%d%d",&n,&m)){
ini();
for(int i=0;i<m;i++){
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
ind[b]++;
add(a,b,w);
}
getCriticalPath();
}
return 0;
}