免费 DIY 之旅问题_chengqiuming

大大的周 02-07 604

一?原问题描述

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?输入样例

0 70 90

1 2

1 3

2 4

3 4

0 90 70

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"); } } } 六测试

绿色为输入，白色为输出