关键路径
了解:关键路径中边表示活动,点表示事件。关键路径主要在求得两个问题1.完成这项工程至少需要多少时间 2.那些活动时关键的
1.求出所有事件的最早发送时间(ve[N]),最迟发生时间(vl[N])
2.根据ve[]和vl[]求出活动的v[]和l[]
3.当某点v[i]=l[i]时就是关键活动
#include<iostream> #include<string.h> #include<algorithm> #include<stack> #define N 100 using namespace std; struct graph{ int a[N][N]; int n; }; int ve[N],vl[N]; stack<int> t; int TopologicalSort(graph g){ int indegree[N],i,j,count; stack<int> s; memset(indegree,0,sizeof(indegree)); count=0; for(i=0;i<g.n;i++) for(j=0;j<g.n;j++) if(g.a[i][j]>0)indegree[j]++; for(i=0;i<g.n;i++)if(!indegree[i]){s.push(i);t.push(i);} while(!s.empty()){ i=s.top(); s.pop(); count++; for(j=0;j<g.n;j++){ if(g.a[i][j]){ indegree[j]--; if(!indegree[j]){s.push(j);t.push(j);} ve[j]=max(ve[i]+g.a[i][j],ve[j]); } } } if(count<g.n)return 0; return 1; } int CriticalPath(graph g){ if(!TopologicalSort(g))return 0; int i,j; int ee,el; char tag; for(i=0;i<g.n;i++)vl[i]=ve[g.n-1]; while(!t.empty()){ i=t.top(); t.pop(); for(j=0;j<g.n;j++)if(g.a[i][j])vl[i]=min(vl[i],vl[j]-g.a[i][j]); } for(i=0;i<g.n;i++){ for(j=0;j<g.n;j++){ if(g.a[i][j]){ ee=ve[i],el=vl[j]-g.a[i][j]; tag=(ee==el)?'*':' '; printf("%d %d %d %d %d %c\n",i+1,j+1,g.a[i][j],ee,el,tag); } } } cout<<endl; for(i=0;i<g.n;i++)cout<<ve[i]<<" "; cout<<endl; for(i=g.n-1;i>=0;i--)cout<<vl[i]<<" "; return 1; } int main(){ graph g; cin>>g.n; int i,j; for(i=0;i<g.n;i++){ for(j=0;j<g.n;j++){ cin>>g.a[i][j]; } } CriticalPath(g); return 0; }
测试数据:
9
0 6 4 5 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 2 0 0 0
0 0 0 0 0 0 9 7 0
0 0 0 0 0 0 0 4 0
0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 4
0 0 0 0 0 0 0 0 0
邻接表+java
import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.Stack; class Edge{ int from; int to; int w; int next; } public class Main{ static Edge[] edges=new Edge[10005]; static int[] head=new int[10005]; public static void add(int from,int to,int w,int i) { edges[i]=new Edge(); edges[i].from=from; edges[i].to=to; edges[i].w=w; edges[i].next=head[from]; head[from]=i; } public static void main(String[] args) { Queue<Integer> que1=new LinkedList<Integer>(); Stack<Integer> que2=new Stack<Integer>(); int[] indegree=new int[10005]; int[] ve=new int[10005];//事件最早 int[] vl=new int[10005];//事件最晚 Scanner sc=new Scanner(System.in); int n,m; int from,to,w; int i,j,top; int ee,el; n=sc.nextInt(); m=sc.nextInt(); for(i=1;i<=n;i++)head[i]=-1; for(i=1;i<=m;i++) { from=sc.nextInt(); to=sc.nextInt(); w=sc.nextInt(); add(from, to, w,i); indegree[to]++; } for(i=1;i<=n;i++) { if(indegree[i]==0) { que1.add(i); que2.add(i); } } while(!que1.isEmpty()) { top=que1.poll(); for(i=head[top];i!=-1;i=edges[i].next) { if(indegree[edges[i].to]>0) { ve[edges[i].to]=Math.max(ve[edges[i].to],ve[top]+edges[i].w); indegree[edges[i].to]--; if(indegree[edges[i].to]==0) { que1.add(edges[i].to); que2.add(edges[i].to); } } } } for(i=1;i<=n;i++)vl[i]=ve[n]; while(!que2.isEmpty()) { top=que2.pop(); for(i=1;i<=n;i++) { for(j=head[i];j!=-1;j=edges[j].next) { if(edges[j].to==top) { vl[edges[j].from]=Math.min(vl[edges[j].from],vl[edges[j].to]-edges[j].w); } } } } for(i=1;i<=n;i++) { for(j=head[i];j!=-1;j=edges[j].next) { ee=ve[i]; el=vl[edges[j].to]-edges[j].w; char tag=ee==el?'*':'X'; System.out.println(i+" "+edges[j].to+" "+ee+" "+el+tag); } } } }
9 11
1 2 6
1 3 4
1 4 5
2 5 1
3 5 1
4 6 2
5 7 9
5 8 7
6 8 4
7 9 2
8 9 4