免费 DIY 之旅问题

一 原问题描述

Free DIY Tour - HDU 1224 - Virtual Judgehttps://vjudge.net/problem/HDU-1224

二 输入和输出

1 输入

第1行是整数 T，表示测试用例数。每个测试用例的第 1 行都是一个整数 N，表示城市数。然后是 N 个整数，表示城市评分。接下来是整数 M，后跟 M 对整数 Ai 和 Bi，表示可以从城市 Ai 直飞城市 Bi。

2 输出

对于每个测试用例，都单行输出评分之和的最大值和最佳 DIY 线路。在测试用例之间都输出一个空行。

三 输入和输出样例

1 输入样例

2

3

0 70 90

4

1 2

1 3

2 4

3 4

3

0 90 70

4

1 2

1 3

2 4

3 4

2 输出样例

CASE 1#

points : 90

circuit : 1->3->1

CASE 2#

points : 90

circuit : 1->2->1

四 分析和设计

1 分析

本问题其实是在求解 1~N+1 的最长路径。根据输出样例 1，构建的图如下图所示。

起点和终点的评分为 0，终点 4 实际上也是起点1，因为起点编号为 1 和 N+1，1 > 3 >1 这条路径的评分之和最大，因此答案为 90。

2 算法设计

可以使用邻接矩阵存储，使用两个 fro 语句更新。也可以使用 SPFA 算法求最长路径。

a 读入每个节点的评分，将第 N+1 个节点的评分设置为 0。

b 读入可以直飞城市编号，采用邻接矩阵存储。

c 枚举 j=1...n+1,i=1...j-1,如果 map[i][j] && dis[j]<dis[i]+qd[j],则

dis[j] = dis[i]+qd[j];

pre[j]=i;

d 递归输出最长的回路

五 代码

package graph.hdu1224;

import java.util.Scanner;

public class Hdu1224 {
    static final int maxn = 105;
    static int qd[] = new int[maxn]; // 有趣点
    static int pre[] = new int[maxn]; //前驱
    static int dis[] = new int[maxn];// 和值
    static int n;
    static int m;

    static int map[][] = new int[maxn][maxn]; // 邻接矩阵

    // 输出最长的回路
    static void printpath(int i) {
        if (i == -1)
            return;
        printpath(pre[i]);
        System.out.print(i + "->");
    }

    public static void main(String[] args) {
        int T, u, v, cas = 0;
        Scanner scanner = new Scanner(System.in);
        T = scanner.nextInt();
        while (T-- >= 0) {
            for (int i = 0; i < pre.length; i++) {
                pre[i] = -1;
            }
            dis = new int[maxn];
            map = new int[maxn][maxn];

            n = scanner.nextInt();

            for (int i = 1; i <= n; i++)
                qd[i] = scanner.nextInt();
            qd[n + 1] = 0;
            m = scanner.nextInt();
            for (int i = 1; i <= m; i++) {
                u = scanner.nextInt();
                v = scanner.nextInt();
                map[u][v] = 1;
            }
            for (int j = 1; j <= n + 1; j++)
                for (int i = 1; i < j; i++)
                    if (map[i][j] == 1 && dis[j] < dis[i] + qd[j]) {
                        dis[j] = dis[i] + qd[j];
                        pre[j] = i;
                    }
            if (cas != 0)
                System.out.println();
            System.out.println("CASE " + ++cas + "#");
            System.out.println("points : " + dis[n + 1]);
            System.out.print("circuit : ");

            printpath(pre[n + 1]); // 最后一个节点，手工输出1，所以从pre[n+1]开始
            System.out.println("1");
        }
    }
}

六 测试

绿色为输入，白色为输出