【HDU No. 1224】 免费DIY之旅

【HDU No. 1224】 免费DIY之旅

杭电OJ还是进不去

看看题目吧直接。

【题意】

旅游公司展示了一种新型DIY线路。

各线路都包含一些可由游客自己选择的城市。根据该公司的统计数据，每个城市都有自己的评分，评分越高越有趣。例如，巴黎的评分是90，纽约的评分是70，等等。世界上不是任何两个城市之间都可以直飞的，因此旅游公司提供了一张地图，告诉游客是否可以在地图上任意两个城市之间直飞。在地图上用一个数字标记每个城市，一个数字较大的城市不能直接飞往数字较小的城市。

薇薇从杭州出发（杭州是第1个城市，也是最后1个城市，所以杭州被标记为1和N +1），它的评分为0。薇薇希望尽可能地让游览变得有趣。

【输入输出】

输入：

第1行是整数T ，表示测试用例数。每个测试用例的第1行都是一个整数N （2≤N ≤100），表示城市数。然后是N 个整数，表示城市的评分。接着是整数M ，后跟M 对整数Ai 、Bi （1≤i ≤M ），表示从城市Ai 可以直飞到城市Bi 。

输出：

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

在测试用例之间都输出一个空行。

【样例】

【思路分析】

这道题其实就是求解 1~N + 1的最长路径。根据输入样例，构建的图如下图所示

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

【算法设计】

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

1. 读入每个节点的评分，将第N +1个节点的评分设置为0。
2. 读入可以直飞的城市编号，采用邻接矩阵存储。
3. 枚举j =1…n +1，i =1…j -1，如果map[i ][j ]&&dis[j]

dis[j] = dis[i] + qd[j];
pre[j] = i;
1
2

4. 递归输出最长的回路

【算法实现】

#include
#include

using namespace std;
#define maxn 110

int qd[maxn];  //有趣点
int pre[maxn] , dis[maxn] , n ,m ; //前驱，和值
int map[maxn][maxn];  //邻接矩阵

void printpath(int i){ //输出最长的回路 
	
	if(i == -1){
		return;
	}
	printpath(pre[i]);
	cout << i << "->";
} 

int main(){
	
	int T, u , v, cas = 0;
	
	cin >> T;
	while(T --){
		
		memset(pre , -1 , sizeof(pre));
		memset(dis , 0 , sizeof(dis));
		memset(map , 0 , sizeof(map));
		
		cin >> n ;
		for(int i = 1;  i <= n ; i++){
			
			cin >> qd[i];
		}
		qd[n + 1] = 0;
		cin >> m;
		for(int i = 1; i <= m ; i++){
			
			cin >> u >> v;
			map[u][v] = 1;
		}
		
		for(int j = 1; j <= n + 1; j ++){
			for(int i = 1; i < j ; i++){
				
				if(map[i][j] && dis[j] < dis[i] + qd[j]){
					
					dis[j] = dis[i] + qd[j];
					pre[j] = i;
				}
			}
		}
		
		if(cas){
			
			cout << endl;
		}
		cout << "CASE " << ++ cas << "#" << endl;
		cout << "points : " << dis[n + 1] << endl;
		cout << "circuit : ";
		
		printpath(pre[n + 1]);  //最后一个节点，手工输出1,所以从 pre[n + 1]开始
		cout << "1" << endl; 
	}
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

跑下样例

OK