题目描述
输入
输出
输入样例
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
输出样例
CASE 1# points : 90 circuit : 1->3->1 CASE 2# points : 90 circuit : 1->2->1
思路:题目的意思是求最长路径.每个点都有一个趣味大小,我们要求的是最大的趣味大小,以及找到其路径(关键路径).
并且旅行路径只能从小往大走,那就说明对于某个点x,其前驱点一定小于该点.所以我们可以使用两个for循环对其进行松弛操作.
图中起始点和最后的终点是一样的,但由于只能往大点走,所以出发点的标号即是1又是N+1
参考代码
#include<iostream> #include<string.h> using namespace std; const int maxn = 110; int map[maxn][maxn],qd[maxn],dis[maxn],p[maxn],T,n,m,u,v;// void printPath(int s){//递归从前往后输出点. if(s==-1){ return; } printPath(p[s]); cout<<s<<"->"; } int main() { cin>>T; for(int k = 1; k <= T;k++){ //数据初始化 memset(map,0,sizeof(map)); memset(qd,0,sizeof(qd)); memset(dis,0,sizeof(dis)); memset(p,-1,sizeof(p)); 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 i = 1;i <= n+1; i++){//对每个节点进行松弛 for(int j = 1;j < i; j++){ if(map[j][i]&&dis[j]+qd[i]>dis[i]){ dis[i] = dis[j]+qd[i]; p[i] = j; } } } cout<<"CASE "<<k<<"#"<<endl; cout<<"points : "<<dis[n+1]<<endl; cout<<"circuit :"<<" "; printPath(p[n+1]);//从最后一个节点的前驱开始往前递归,依次输出节点. cout<<1<<endl; if(k!=T){ cout<<endl; } } return 0; }
