一 原问题链接

SDUT OnlineJudgeAn awesome online judge platform

https://acm.sdut.edu.cn/onlinejudge3/problems/2498

二 输入和输出

1 输入

输入包含多组数据。第 1 行包含节点数 n 和边数 m，接下来的 m 行，包含每条边的起点 s 和终点 e，权值 w。数据保证图连通，且只有一个源点和汇点。

2 输出

单行输出关键路径的权值和，并且从源点输出关键路径上的路径（如果有多条，则输出字典序最小的。）

三 输入和输出样例

1 输入样例

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

2 输出样例

18

1 2

2 5

5 7

7 9

四 分析

本问题求解关系路径实际上就是求解最长路径。求解最长路径时可以将权值加负号求解最短路径，也可以改变松弛条件，若距离较大则更新。

对于有向无环图，可以按拓扑序列松弛求解最长路径，也可以用 Bellman 或 SPFA 算法权值加负号求解最短路径，或者改变松弛条件求解最长路径。

对于有向有环图，可以用 Bellman 或 SPFA 算法判断环，若有正环，则不存在最长路径。

Dijkstra 算法不可以用于处理负权边，也无法通过改变松弛条件得到最长路径。该问题需要输出路径，而且该路径需要按字典序选取，所以反向简图会更便于记录路径。

路径的字典序最小就是走到一个点，继续向下走一步时，选择编号最小的，这就是字典序，但是在最短路径的更新过程中，如果 dis[y]==dis[x]+w&&x<pre[y]，路径长度相等但是 x 比 y 的前驱编号更小，则更新 y 的前驱节点为 x，即 pre[y] =x。

在本问题中，V5-V7-V9 和 V5-V8-V9 的路径长度是一样的，按字典序应该走前者。如果逆向走，从 V9 到 V7，则 dis[7] = 2 ; 从 V9 到 V8，则 dis[8] = 4; 从 V8 到 V5，则 dis[5]=11,pre[5]=8;从 V7 到 V5，则 dis[7]+9=11=dis[5],但是 7 比 8 的字典序小，更新 5 的前驱为 7，pre[5]=7。

在原图的逆向图上，从后向前走一条最长路径，然后根据前驱数组，1 的前驱为 2，输出1 2 , 2 的前驱是 5，输出 2 5, 5 的前驱是7，输出 5 7, 7 的前驱是 9，输出 7 9。

五 算法设计

1 建立原图的逆向图。检查入度为 0的节点 s 和出度为 0 的节点 t

2 使用 SPFA 算法求最长路径。如果 dis[y]<dis[x]+e[i].w||dis[y]==dis[x]+e[i].w && x<pre[y],则 更新 dis[y]=dis[x]+e[i].w;pre[y]=x;

六 代码

package graph.sdutoj2498;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Sdutoj2498 {
    static final int maxn = 10010;
    static final int maxe = 50010;
    static int n;
    static int m;
    static int cnt;
    static int head[] = new int[maxn]; // 链式前向星头
    static int dis[] = new int[maxn]; // 距离
    static int pre[] = new int[maxn]; // 前驱
    static int in[] = new int[maxn]; // 入度
    static int out[] = new int[maxn]; // 出度
    static boolean inq[] = new boolean[maxn]; // 标记是否在队列中
    static node[] e = new node[maxe];
    static {
        for (int i = 0; i < e.length; i++) {
            e[i] = new node();
        }
    }
    static void add(int u, int v, int w) {
        e[++cnt].to = v;
        e[cnt].next = head[u];
        head[u] = cnt;
        e[cnt].w = w;
    }
    static void spfa(int u) {
        Queue<Integer> q = new LinkedList<>();
        q.add(u);
        inq[u] = true;
        while (!q.isEmpty()) {
            int x = q.peek();
            q.poll();
            inq[x] = false;
            for (int i = head[x]; i > 0; i = e[i].next) {
                int y = e[i].to;
                if (dis[y] < dis[x] + e[i].w || (dis[y] == dis[x] + e[i].w && x < pre[y])) {
                    dis[y] = dis[x] + e[i].w;
                    pre[y] = x;
                    if (!inq[y]) {
                        q.add(y);
                        inq[y] = true;
                    }
                }
            }
        }
    }
    public static void main(String[] args) {
        int u, v, w, s = 0, t = 0;
        while (true) {
            Scanner scanner = new Scanner(System.in);
            n = scanner.nextInt();
            m = scanner.nextInt();
            head = new int[maxn]; // 链式前向星头
            dis = new int[maxn]; // 距离
            inq = new boolean[maxn];
            in = new int[maxn]; // 入度
            out = new int[maxn]; // 出度
            for (int i = 0; i < pre.length; i++) {
                pre[i] = -1;
            }
            cnt = 0;
            for (int i = 0; i < m; i++) {
                u = scanner.nextInt();
                v = scanner.nextInt();
                w = scanner.nextInt();
                add(v, u, w);
                out[v]++;
                in[u]++;
            }
            for (int i = 1; i <= n; i++) {
                if (in[i] == 0) s = i;
                if (out[i] == 0) t = i;
            }
            spfa(s);
            System.out.println(dis[t]);
            int k = t;
            while (pre[k] != -1) {
                System.out.println(k + " " + pre[k]);
                k = pre[k];
            }
        }
    }
}
class node {
    int to;
    int w;
    int next;
}

七 测试