HDU 1224 Free DIY Tour

题意：给出每个城市interesting的值，和城市之间的飞行路线，求一条闭合路线（从原点出发又回到原点）

使得路线上的interesting的值之和最大

因为要输出路径，所以用pre数组来保存前驱

在输出路径的时候，我是把前驱一次放在route数组里面，然后再将整个数组反转过来

另外，看别人的题解里面还有一种递归的方法求路径，挺有新意，学习了

我的做法：

 1 //#define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 const int maxn = 5100;
 9 bool flight[110][110];
10 int city[110];
11 int dp[110];
12 int pre[110];
13 int route[110];
14 
15 int main(void)
16 {
17     #ifdef LOCAL
18         freopen("1224in.txt", "r", stdin);
19     #endif
20 
21     int N, kase;
22     scanf("%d", &N);
23     for(kase = 1; kase <= N; ++kase)
24     {
25         if(kase > 1)    printf("
");
26 
27         int n;
28         scanf("%d", &n);
29         int i;
30         for(i = 1; i <= n; ++i)
31             scanf("%d", &city[i]);
32         city[n + 1] = 0;
33         
34         int m, from, to;
35         memset(flight, 0, sizeof(flight));
36         scanf("%d", &m);
37         for(i = 1; i <= m; ++i)
38         {
39             scanf("%d%d", &from, &to);
40             flight[from][to] = true;
41         }
42 
43         memset(dp, 0, sizeof(dp));
44         memset(pre, 0, sizeof(pre));
45         int j;
46         for(i = 2; i <= n + 1; ++i)
47             for(j = 1; j < i; ++j)
48                 if(flight[j][i]
49                     && (dp[j] + city[i]) > dp[i])
50                 {
51                     dp[i] = dp[j] + city[i];
52                     pre[i] = j;
53                 }
54                     
55         
56         printf("CASE %d#
", kase);
57         printf("points : %d
", dp[n + 1]);
58         int p = n + 1, len = 0;
59         while(pre[p] != 0)
60         {
61             route[len++] = pre[p];
62             p = pre[p];
63         }
64         for(i = 0; i < len / 2; ++i)
65         {
66             int t = route[i];
67             route[i] = route[len - i -1];
68             route[len - i -1] = t;
69         }
70         
71         printf("circuit : ");
72         for(i = 0; i < len; ++i)
73             printf("%d->", route[i]);
74         printf("1
");
75     }
76 
77     return 0;
78 }

代码君

别人递归回溯输出路径的做法：

 1 //#define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 const int maxn = 5100;
 9 bool flight[110][110];
10 int city[110];
11 int dp[110];
12 int pre[110];
13 int route[110];
14 
15 void putroute(int p)
16 {
17     if(p == 0)
18         return;
19     putroute(pre[p]);
20     printf("%d->", p);
21 }
22 
23 int main(void)
24 {
25     #ifdef LOCAL
26         freopen("1224in.txt", "r", stdin);
27     #endif
28 
29     int N, kase;
30     scanf("%d", &N);
31     for(kase = 1; kase <= N; ++kase)
32     {
33         if(kase > 1)    printf("
");
34 
35         int n;
36         scanf("%d", &n);
37         int i;
38         for(i = 1; i <= n; ++i)
39             scanf("%d", &city[i]);
40         city[n + 1] = 0;
41         
42         int m, from, to;
43         memset(flight, 0, sizeof(flight));
44         scanf("%d", &m);
45         for(i = 1; i <= m; ++i)
46         {
47             scanf("%d%d", &from, &to);
48             flight[from][to] = true;
49         }
50 
51         memset(dp, 0, sizeof(dp));
52         memset(pre, 0, sizeof(pre));
53         int j;
54         for(i = 2; i <= n + 1; ++i)
55             for(j = 1; j < i; ++j)
56                 if(flight[j][i]
57                     && (dp[j] + city[i]) > dp[i])
58                 {
59                     dp[i] = dp[j] + city[i];
60                     pre[i] = j;
61                 }
62                     
63         
64         printf("CASE %d#
", kase);
65         printf("points : %d
", dp[n + 1]);
66 
67         printf("circuit : ");
68         putroute(pre[n + 1]);
69         printf("1
");
70     }
71 
72     return 0;
73 }

代码君