题目描述
一个无环的有向图称为无环图（Directed Acyclic Graph），简称DAG图。 AOE(Activity On Edge)网：顾名思义，用边表示活动的网，当然它也是DAG。与AOV不同，活动都表示在了边上，如下图所示： 如上所示，共有11项活动（11条边），9个事件（9个顶点）。整个工程只有一个开始点和一个完成点。即只有一个入度为零的点（源点）和只有一个出度为零的点（汇点）。 关键路径：是从开始点到完成点的最长路径的长度。路径的长度是边上活动耗费的时间。如上图所示，1 到2 到 5到7到9是关键路径（关键路径不止一条，请输出字典序最小的），权值的和为18。
输入
这里有多组数据，保证不超过10组，保证只有一个源点和汇点。输入一个顶点数n(2<=n<=10000),边数m(1<=m <=50000),接下来m行，输入起点sv，终点ev,权值w（1<=sv,ev<=n,sv != ev,1<=w <=20)。数据保证图连通。
输出
关键路径的权值和，并且从源点输出关键路径上的路径（如果有多条，请输出字典序最小的）。
示例输入
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
好久做过的题了，不过今天拿出来看看觉得这个题挺好，它是逆向建图和打印路径，求最长路径；最长路径用SPFA求解，但注意初始化为最小。
1 #include<stdio.h>
2 #include<
string.h>
3 #include<iostream>
4 #include<queue>
5 #include<vector>
6 using namespace std;
7
8 const int INF =
0x3f3f3f3f;
9 const int MAX =
10000;
10
11 struct edge
12 {
13 int to,w;
14 };
15
16 struct node
17 {
18 int indegree;
19 int outdegree;
20 }V[MAX+
10];
21
22 int n,m;
23 int inque[MAX+
10],dis[MAX+
10];
24 int pre[MAX+
10];
25 vector<edge>map[MAX+
10];
26
27 void spfa(
int s)
28 {
29 queue<
int>
que;
30 memset(inque,
0,
sizeof(inque));
31 for(
int i =
1; i <= n; i++
)
32 dis[i] = -INF;
//注意初始化
33 dis[s] =
0;
34 que.push(s);
35 inque[s] =
1;
36 while(!
que.empty())
37 {
38 int u =
que.front();
39 que.pop();
40 inque[u] =
0;
41 for(
int i =
0; i < map[u].size(); i++
)
42 {
43 int to =
map[u][i].to;
44 if(dis[u] > -INF && (dis[to] < map[u][i].w + dis[u] || (dis[to] == map[u][i].w + dis[u] && u <
pre[to])))
45 {
46 dis[to] = map[u][i].w +
dis[u];
47 pre[to] =
u;
48 if(inque[to] ==
0)
49 {
50 que.push(to);
51 inque[to] =
1;
52 }
53 }
54 }
55 }
56 }
57
58 int main()
59 {
60 int u,v,w,s,t;
61 while(~scanf(
"%d %d",&n,&
m))
62 {
63 memset(pre,
0x3f,
sizeof(pre));
64 for(
int i =
1; i <= n; i++
)
65 map[i].clear();
66 for(
int i =
1; i <= n; i++
)
67 {
68 V[i].indegree =
0;
69 V[i].outdegree =
0;
70 }
71 for(
int i =
1; i <= m; i++
)
72 {
73 //逆向建图
74 scanf(
"%d %d %d",&u,&v,&
w);
75 map[v].push_back((
struct edge){u, w});
76 V[v].outdegree++
;
77 V[u].indegree++
;
78 }
79 for(
int i =
1; i <= n; i++
)
80 {
81 if(V[i].indegree ==
0)
82 s =
i;
83 if(V[i].outdegree ==
0)
84 t =
i;
85 }
86 spfa(s);
87 printf(
"%d\n",dis[t]);
88 int x =
t;
89 //打印路径
90 while(x !=
s)
91 {
92 printf(
"%d %d\n", x, pre[x]);
93 x =
pre[x];
94 }
95 }
96 return 0;
97 }
View Code
转载于:https://www.cnblogs.com/LK1994/p/3414712.html
