双语网站系统torrentkitty搜索引擎

AOE网

用顶点表示事件，弧表示活动，弧的权表示活动持续时间

关键路径

从源点（入度为0）到汇点（出度为0）最长的路径

路径长度

路径上各活动持续时间之和（权值之和）

求解关键路径

1、首先需要定义四个描述量

    ve(j)  : 表示事件 j (用顶点表示） 最早发生时间

    例如：

ve(v1)=0,  ve(v2)=30

vl(j) : 表示事件j的最迟发生时间

vl(v4) =165

e(i) 表示活动（用弧表示）最早开始时间

 e(a3)=30

l(i) 表示活动开始的最迟时间

l(a3)=120

完成活动ai 的时间余量

=l(i) - e(i)

关键活动

关键路径上的活动，即l(i)==e(i) 的活动

2、如何找l(i)==e(i) 的关键活动

设活动ai 用弧<j,k>表示，其持续时间记为 w

e(i) = ve(i) ; l(i) = vl(k) - w;

ve(i) = max{ ve(j) + w }

vl(i) = min{ vl(k) - w }

步骤：

1.首先进行拓扑排序

2.根据拓扑排序的顺序求vi和vl

3.求l和e

下面是代码（没有检测正确性）

	#include<iostream>
#include<map>
#include<queue>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int n,m;
vector<int> v[120];
queue<int> q;
//邻接表 
struct Edge{int to,dis,next;//next用来存储i顶点的其他边的编号 
}e[1000];
int head[1000];//用来存储i顶点出现的最后一条边的编号
int num;//边的编号 
void add(int from,int to,int dis){e[++num].next=head[from];e[num].to=to;e[num].dis=dis;head[from]=num;//对i顶点的最新出现所在边的编号更新 
}
//拓扑排序 
int indre[1000]; 
int top[1000],cnt;
void toposort(){for(int i=1;i<=n;i++){if(indre[i]==0)q.push(i);}while(!q.empty()){int k=q.front();q.pop();top[++cnt]=k;for(int i=head[k];i!=0;i=e[i].next){--indre[e[i].to];if(indre[e[i].to]==0)q.push(e[i].to);}} 
}
int ve[1000];
int vl[1000];
void keypath(){//*******求所有点的ve********** for(int i=1;i<=n;i++){int k=top[i];//依次更新与k的所有邻接顶点的最早发生时间 for(int j=head[k];j!=0;j=e[j].next){int p=e[j].to;int w=e[j].dis;if(ve[p]<ve[k]+w)ve[p]=ve[k]+w;}}//初始化所有点的vl for(int i=1;i<=n;i++){vl[i]=ve[n];} //**********求所有点的vl***** for(int i=n;i>=1;i++){int k=top[i];for(int j=head[j];j!=0;j=e[j].next){int p=e[j].to;int w=e[j].dis;if(vl[k]>vl[p]-w)vl[k]=vl[k]-w;}}//******求出关键活动******for(int i=1;i<=n;i++){for(int j=head[i];j!=0;j=e[i].next){int p=e[j].to;int w=e[j].dis;int l=vl[j]-w;//求l if(l==ve[i])cout<<i<<"->"<<p<<endl;//输出关键活动 }} 
}
int main(){cin>>n>>m;for(int i=1;i<=m;i++){int x,y,v;cin>>x>>y>>v;add(x,y,v);++indre[y];}toposort();keypath();return 0; 
}