题意：给出每个城市interesting的值，和城市之间的飞行路线，求一条闭合路线（从原点出发又回到原点）
使得路线上的interesting的值之和最大
因为要输出路径，所以用pre数组来保存前驱
在输出路径的时候，我是把前驱一次放在route数组里面，然后再将整个数组反转过来
另外，看别人的题解里面还有一种递归的方法求路径，挺有新意，学习了
我的做法：
//#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = ;
bool flight[][];
int city[];
int dp[];
int pre[];
int route[]; int main(void)
{
#ifdef LOCAL
freopen("1224in.txt", "r", stdin);
#endif int N, kase;
scanf("%d", &N);
for(kase = ; kase <= N; ++kase)
{
if(kase > ) printf("\n"); int n;
scanf("%d", &n);
int i;
for(i = ; i <= n; ++i)
scanf("%d", &city[i]);
city[n + ] = ; int m, from, to;
memset(flight, , sizeof(flight));
scanf("%d", &m);
for(i = ; i <= m; ++i)
{
scanf("%d%d", &from, &to);
flight[from][to] = true;
} memset(dp, , sizeof(dp));
memset(pre, , sizeof(pre));
int j;
for(i = ; i <= n + ; ++i)
for(j = ; j < i; ++j)
if(flight[j][i]
&& (dp[j] + city[i]) > dp[i])
{
dp[i] = dp[j] + city[i];
pre[i] = j;
} printf("CASE %d#\n", kase);
printf("points : %d\n", dp[n + ]);
int p = n + , len = ;
while(pre[p] != )
{
route[len++] = pre[p];
p = pre[p];
}
for(i = ; i < len / ; ++i)
{
int t = route[i];
route[i] = route[len - i -];
route[len - i -] = t;
} printf("circuit : ");
for(i = ; i < len; ++i)
printf("%d->", route[i]);
printf("1\n");
} return ;
}
代码君
别人递归回溯输出路径的做法：
//#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = ;
bool flight[][];
int city[];
int dp[];
int pre[];
int route[]; void putroute(int p)
{
if(p == )
return;
putroute(pre[p]);
printf("%d->", p);
} int main(void)
{
#ifdef LOCAL
freopen("1224in.txt", "r", stdin);
#endif int N, kase;
scanf("%d", &N);
for(kase = ; kase <= N; ++kase)
{
if(kase > ) printf("\n"); int n;
scanf("%d", &n);
int i;
for(i = ; i <= n; ++i)
scanf("%d", &city[i]);
city[n + ] = ; int m, from, to;
memset(flight, , sizeof(flight));
scanf("%d", &m);
for(i = ; i <= m; ++i)
{
scanf("%d%d", &from, &to);
flight[from][to] = true;
} memset(dp, , sizeof(dp));
memset(pre, , sizeof(pre));
int j;
for(i = ; i <= n + ; ++i)
for(j = ; j < i; ++j)
if(flight[j][i]
&& (dp[j] + city[i]) > dp[i])
{
dp[i] = dp[j] + city[i];
pre[i] = j;
} printf("CASE %d#\n", kase);
printf("points : %d\n", dp[n + ]); printf("circuit : ");
putroute(pre[n + ]);
printf("1\n");
} return ;
}
代码君