题目描述
一个无环的有向图称为无环图（Directed Acyclic Graph），简称DAG图。
AOE(Activity On Edge)网：顾名思义，用边表示活动的网，当然它也是DAG。与AOV不同，活动都表示在了边上，如下图所示：
如上所示，共有11项活动（11条边），9个事件（9个顶点）。整个工程只有一个开始点和一个完成点。即只有一个入度为零的点（源点）和只有一个出度为零的点（汇点）。
关键路径：是从开始点到完成点的最长路径的长度。路径的长度是边上活动耗费的时间。如上图所示，1 到2 到 5到7到9是关键路径（关键路径不止一条，请输出字典序最小的），权值的和为18。
Input
这里有多组数据，保证不超过10组，保证只有一个源点和汇点。输入一个顶点数n(2<=n<=10000),边数m(1<=m <=50000),接下来m行，输入起点sv，终点ev,权值w（1<=sv,ev<=n,sv != ev,1<=w <=20)。数据保证图连通。
Output
关键路径的权值和，并且从源点输出关键路径上的路径（如果有多条，请输出字典序最小的）。
输入样例
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 8 9 4 7 9 2
输出样例
18 1 2 2 5 5 7 7 9
思路:
这个题的意思是让求源点和汇点的关键路径并输出,当有多条时,输出字典序最小的那个.
求最长路径,可以将权值加负号来求解,也可以改变松弛条件,距离大的更新.而Dijkstra算法无法处理负权边,也没有办法通过改变松弛条件来求解最长路(因为它用到了贪心的思想).求解最长路有一下两种方法:
按照拓扑序列求解最长路.
按照Bellman或SPFA算法,改变松弛条件,求解最长路.
但由于Bellman算法时间复杂度是O( n * m),可能会超时,所以为了减少复杂度需要使用SPFA算法,该复杂度是O(k * m),k是一个很小的数,最多为O(n*m)
其次由于要输出路径,而且路径要按照字典序选取,所以反向建图会更方便的输出(如果正向建图则需要借助于栈来进行输出,如果数据量大,可能通不过)
我们在进行前驱节点进行编号时,如果该节点的邻接点+中间的边后dis更长,则更新dis和前驱p.如果路径相等,但该节点的号更小则仍只更新前驱p.
这个题也可以使用Bellman-Ford实现.还可以一边求拓扑一边进行松弛,后序进行补充!
参考代码
#include<iostream> #include<string.h> #include<queue> #include<stack> using namespace std; const int maxv = 10000+10,maxe = 50000+10,INF = 0xc0c0c0c0; int head[maxv],dis[maxv],p[maxv],in[maxv],out[maxv],vis[maxv],num,n,m; struct Edge{ int next,to,w; }e[maxe]; void add(int u,int v,int w){ e[++num].to = v; e[num].w = w; e[num].next = head[u]; head[u] = num; } void SPFA(int u){ for(int i = 1; i <= n; i++){ dis[i] =INF; } queue<int> q; q.push(u); vis[u] = 1; dis[u] = 0; p[u] = -1; while(!q.empty()){ int x = q.front(); q.pop(); vis[x] = 0; for(int i = head[x]; i ;i = e[i].next){ if(dis[e[i].to]<dis[x]+e[i].w || (dis[e[i].to]==dis[x]+e[i].w&&p[e[i].to] > x)){ dis[e[i].to] = dis[x]+e[i].w; p[e[i].to] = x; if(!vis[e[i].to]){//如果没有访问过就入队列. q.push(e[i].to); vis[e[i].to] = 1; } } } } } int main() { stack<int> stack1; int u,v,w,s,t,k; while(cin>>n>>m){ //初始化 memset(head,0,sizeof(head)); memset(dis,0xc0,sizeof(head)); memset(p,-1,sizeof(p)); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); memset(vis,0,sizeof(vis)); num = 0; for(int i = 1;i <= m; i++){ cin>>v>>u>>w; add(u,v,w); in[v]++; out[u]++; } for(int i = 1;i <= n; i++){ if(in[i]==0){ s = i; } if(out[i]==0){ t = i; } } SPFA(s); cout<<dis[t]<<endl; k = t; while(p[k]!=-1){//这里必须进行反向建边. 按说正向+栈也可以,但运行却不行.可能时间复杂度太高了.如果逆向建边,则直接从前往后输出即可,不需要使用栈. cout<<k<<" "<<p[k]<<endl; k = p[k]; } // while(p[k]!=-1){ // stack1.push(k); // stack1.push(p[k]); // k = p[k]; // } // while(!stack1.empty()){ // //stack1.top(); // cout<<stack1.top()<<" "; // stack1.pop(); // cout<<stack1.top()<<endl; // stack1.pop(); // } } return 0; }
参考代码2(Bellman-Ford)
#include<iostream> #include<string.h> using namespace std; const int maxe = 50000+10,maxn = 10000+10; struct node{ int u,v,w; }e[maxe]; //边集数组 int dis[maxn],p[maxn],in[maxn],out[maxn],n,m,s,t; void Bellman_Ford(){ int temp = 0; for(int i = 0;i < n-1; i++){//n-1次松弛 temp = 0; for(int j = 1; j <= m; j++){ if((dis[e[j].v] < dis[e[j].u]+e[j].w)||(dis[e[j].v] == dis[e[j].u]+e[j].w &&p[e[j].v] > e[j].u)){//如果①路径更大 ②路径长度相等,但前驱节点可以更小.满足任意一个都可进行更新. dis[e[j].v] = dis[e[j].u] + e[j].w; p[e[j].v] = e[j].u; temp = 1; } } if(!temp){//如果某一轮,没有发生更新则说明已跟新完毕. break; } } } int main() { int u,v,w,cnt; while(cin>>n>>m){ //数据初始化 memset(dis,0,sizeof(dis)); memset(p,-1,sizeof(p)); memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); cnt = 0; for(int i = 1; i <=m; i++){ cin>>v>>u>>w;//建立反向图 e[++cnt].u = u; e[cnt].v = v; e[cnt].w = w; in[v]++; out[u]++; } for(int i = 1; i <= n; i++){ if(!in[i]){ s = i; } if(!out[i]){ t = i; } } Bellman_Ford(); cout<<dis[t]<<endl; int k = t; //输出关键路径 while(p[k]!=-1){ cout<<k<<" "<<p[k]<<endl; k = p[k]; } } return 0; }
