一道很好的dfs加储存路径的题目 ：路径保存：每次dfs都存i 当大于max时 将临时数组保存到答案数组
并不是当 当前值大于最大值时更新路径
还要加上一个条件：能回去
#include<bits/stdc++.h> using namespace std; int n; int m1[200][200]; int valu[105]; int ans[105];int path[105]; int maxi,len; void dfs(int stepn,int sum,int cur) { for(int i=cur+1;i<=n;i++) { if(m1[cur][i]) { path[stepn]=i; if(m1[i][n+1]) { path[stepn+1]=1; if(sum+valu[i]>maxi) { maxi=sum+valu[i]; len=stepn+1; for(int j=1;j<=len;j++) { ans[j]=path[j]; } } } dfs(stepn+1,sum+valu[i],i); } } } int main() { int cas;scanf("%d",&cas);int case1=1; while(cas--) { maxi=0; len=1; ans[0]=1; memset(m1,0,sizeof(m1)); scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&valu[i]); valu[1]=valu[1+n]=0; int q; scanf("%d",&q); while(q--) { int a,b; scanf("%d%d",&a,&b); m1[a][b]=m1[b][a]=1; } if(case1!=1) printf(" "); printf("CASE %d# ",case1++); dfs(1,0,1); printf("points : %d ",maxi); if(len!=1) { printf("circuit : "); for(int i=0;i<len;i++) printf("%d->",ans[i]); printf("%d ",ans[len]); } } return 0; }
还可以用dp来做
#include <stdio.h> #include <string.h> bool link[105][105]; int intrest[105], dp[105], last[105], path[105]; int main() { int t, case_num = 1; //freopen("input.txt", "r", stdin); scanf("%d", &t); while(t--) { int n, m, i, j; memset(link, 0, sizeof(link)); memset(dp, 0, sizeof(dp)); last[1] = 0; //last记录上一个走的城市的标号，last[1] = 0是为了让追溯到第一个城市之后就不继续追溯了 scanf("%d", &n); if(case_num != 1) printf(" "); for(i = 1; i <= n; i++) { scanf("%d", &intrest[i]); } intrest[i] = 0; //注意i城市有趣度为0!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! scanf("%d", &m); for(int i = 0; i < m; i++) { int a, b; scanf("%d%d", &a, &b); link[a][b] = link[b][a] = 1; } for(i = 2; i <= n+1; i++) //假设目标城市标号为i(注意到达它之前经过的城市的标号都小于它) { for(j = 1; j < i; j++) //遍历到达i城市之前所在的城市的标号的所有可能性， //更新到达i城的时候的有趣度之和为所有情况中最大的 { if(dp[j]+intrest[i] > dp[i] && link[i][j]) { dp[i] = dp[j]+intrest[i]; last[i] = j; } } } j = 0; i = n+1; while(last[i]) { path[j++] = last[i]; i = last[i]; } printf("CASE %d# ", case_num++); printf("points : %d ", dp[n+1]); printf("circuit : "); for(i = j-1; i >= 0; i--)//注意输出的个数并非为城市数目！！！！！！！！！！！！！ { printf("%d->", path[i]); } printf("1 "); } return 0; }
回顾
#include<iostream> #include<queue> #include<cstdio> #include<cstring> #include<vector> #include<map> #include<algorithm> #include<cmath> using namespace std; #define N 105 #define inf 0x3f3f3f3f int ans[N]; int path[N]; int n,maxx; int mp[N][N]; int city[N]; int len; void dfs(int cur,int interest,int num) { for(int i=cur+1;i<=n;i++) { if(mp[cur][i]) { int t=interest+city[i]; path[num]=i; if(t>maxx&&mp[i][n+1]) { maxx=t; for(int i=0;i<=num;i++) ans[i]=path[i]; len=num; } dfs(i,t,num+1); } } } int main() { int cas;cin>>cas; for(int kase=1;kase<=cas;kase++) { memset(mp,0,sizeof mp); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&city[i]); city[n+1]=city[1]=0; int m,a,b; cin>>m; while(m--) { scanf("%d%d",&a,&b); mp[a][b]=mp[b][a]=1; } path[0]=1; maxx=0; dfs(1,0,1); if(kase!=1)printf(" "); printf("CASE %d# ",kase); printf("points : %d circuit : ",maxx); for(int i=0;i<=len;i++) printf("%d->",ans[i]); printf("%d ",1); } }