【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算法求最长路径。
- 读入每个节点的评分,将第N +1个节点的评分设置为0。
- 读入可以直飞的城市编号,采用邻接矩阵存储。
- 枚举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;
- 递归输出最长的回路
【算法实现】
#include<iostream>
#include<cstring>
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;
}
跑下样例
OK