本文主要是介绍sdut2498--AOE网上的关键路径（spfa+最小字典序），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
AOE网上的关键路径
Time Limit: 1000MS Memory limit: 65536K
题目描述
一个无环的有向图称为无环图（Directed Acyclic Graph），简称DAG图。
AOE(Activity On Edge)网：顾名思义，用边表示活动的网，当然它也是DAG。与AOV不同，活动都表示在了边上，如下图所示：
如上所示，共有11项活动（11条边），9个事件（9个顶点）。整个工程只有一个开始点和一个完成点。即只有一个入度为零的点（源点）和只有一个出度为零的点（汇点）。
关键路径：是从开始点到完成点的最长路径的长度。路径的长度是边上活动耗费的时间。如上图所示，1 到2 到 5到7到9是关键路径（关键路径不止一条，请输出字典序最小的），权值的和为18。
输入
输出
示例输入
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
由题意可以知道这是要求从起点s到终点e的最长路径，因为有10000个点，有50000条边，用spfa进行最短路，但是有一个问题就是要求路径的字典序最小。
解决方式：
倒序建图，当松弛时（u，v），遇到相同的情况，尽量使u变的更小，那么最终得到就是最小的字典序。
对于求最长路径，将dis设为-INF，dis[s] = 0
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std ;
#define INF 0x3f3f3f3f
struct node{int v , w ;int next ;
}p[60000];
queue <int> que ;
int head[11000] , cnt , dis[11000] , vis[11000] ;
int pre[11000] ;
int in[110000] , out[11000] ;
int pri[110000] , num ;
void add(int u,int v,int w)
{p[cnt].v = v ;p[cnt].w = w ;p[cnt].next = head[u] ;head[u] = cnt++ ;return ;
}
void spfa(int s,int e,int n)
{int i , j , u , v ;memset(dis,-INF,sizeof(dis)) ;memset(pre,INF,sizeof(pre)) ;memset(vis,0,sizeof(vis)) ;while( !que.empty() )que.pop();que.push(s) ;dis[s] = 0 ;vis[s] = 1 ;while( !que.empty() ){u = que.front() ;que.pop() ;vis[u] = 0 ;for( i = head[u] ; i != -1 ; i = p[i].next ){v = p[i].v ;if( dis[v] < dis[u] + p[i].w || ( dis[v] == dis[u] + p[i].w && u < pre[v] ) ){dis[v] = dis[u] + p[i].w ;pre[v] = u ;if( vis[v] == 0 ){vis[v] = 1 ;que.push( v ) ;}}}}printf("%d\n", dis[e] ) ;num = 0 ;for( i = e; i != INF ; i = pre[i] )pri[num++] = i ;for(i = 1 ; i < num ; i++){printf("%d %d\n", pri[i-1], pri[i] ) ;}return ;
}
int main()
{int n , m , i , j , u , v , w ;while( scanf("%d %d", &n, &m) != EOF ){cnt = 0 ;memset(head,-1,sizeof(head)) ;memset(in,0,sizeof(in)) ;memset(out,0,sizeof(out)) ;while( m-- ){scanf("%d %d %d", &u, &v, &w);add(v,u,w) ;in[u]++ ;out[v]++ ;}for(i = 1 ; i <= n ; i++){if( !in[i] )u = i ;if( !out[i] )v = i ;}spfa(u,v,n);}return 0;
}
这篇关于sdut2498--AOE网上的关键路径（spfa+最小字典序）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
