One   Link to original question

SDUT OnlineJudgeAn awesome online judge platformhttps://acm.sdut.edu.cn/onlinejudge3/problems/2498

Two   Input and output

1  Input

The input contains multiple sets of data . The first 1  Number of nodes in row  n  And the number of sides  m, Next  m  That's ok , Include the starting point of each edge  s  And the end e, A weight  w. Data ensures graph connectivity , And there is only one source and sink .

2  Output

The weight sum of the critical path is output in a single line , And output the path on the critical path from the source （ If there are more than one , Then output the one with the smallest dictionary order .）

3、 ... and Input and output examples

1  sample input

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  sample output

18

1 2

2 5

5 7

7 9

Four   analysis

The problem solving relationship path is actually solving the longest path . When solving the longest path, you can add a negative sign to the weight to solve the shortest path , You can also change the relaxation conditions , If the distance is large, update .

For directed acyclic graphs , The longest path can be relaxed according to the topological sequence , It can also be used.  Bellman  or  SPFA  Algorithm weight plus minus sign to solve the shortest path , Or change the relaxation condition to solve the longest path .

For directed cyclic graphs , It can be used  Bellman  or  SPFA  Algorithm judgment loop , If there is a positive ring , Then there is no longest path .

Dijkstra  The algorithm cannot be used to deal with negative weighted edges , Nor can we get the longest path by changing the relaxation condition . This problem requires an output path , And the path needs to be selected in dictionary order , So the reverse diagram will be more convenient to record the path .

The smallest dictionary order of the path is to go to a point , When you continue to take a step down , Choose the one with the smallest number , This is the dictionary order , But in the process of updating the shortest path , If  dis[y]==dis[x]+w&&x<pre[y], The path length is equal but  x  Than  y  The precursor number of is smaller , Update  y  The precursor node of is  x, namely  pre[y] =x.

In this question ,V5-V7-V9  and  V5-V8-V9  The length of the path is the same , According to the dictionary order, we should take the former . If you go backwards , from  V9  To  V7, be  dis[7] = 2 ; from  V9 To  V8, be dis[8] = 4; from  V8  To  V5, be  dis[5]=11,pre[5]=8; from  V7  To V5, be  dis[7]+9=11=dis[5], however 7  Than 8  The dictionary order is small , to update 5  The precursor of 7,pre[5]=7.

On the reverse of the original , Take the longest path forward from behind , Then according to the precursor array ,1 The precursor of 2, Output 1 2 , 2 The precursor to this is 5, Output 2 5, 5 The precursor to this is 7, Output 5 7, 7 The precursor to this is 9, Output 7 9.

5、 ... and   Algorithm design

1  Create the reverse diagram of the original drawing . Check penetration 0 The node of s And the output is 0 The node of t

2  Use  SPFA  Algorithm to find the longest path . If  dis[y]<dis[x]+e[i].w||dis[y]==dis[x]+e[i].w && x<pre[y], be   to update  dis[y]=dis[x]+e[i].w;pre[y]=x;

6、 ... and Code

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]; //  Chain forward star head 
    static int dis[] = new int[maxn]; //  distance 
    static int pre[] = new int[maxn]; //  Forerunner 
    static int in[] = new int[maxn]; //  The degree of 
    static int out[] = new int[maxn]; //  The degree of 
    static boolean inq[] = new boolean[maxn]; //  Mark whether it is in the queue 

    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]; //  Chain forward star head 
            dis = new int[maxn]; //  distance 
            inq = new boolean[maxn];
            in = new int[maxn]; //  The degree of 
            out = new int[maxn]; //  The degree of 
            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;
}

7、 ... and test