本文主要是介绍hdu 1224 Free DIY Tour(最长路/dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=1224
基础的求最长路以及记录路径。感觉dijstra不及spfa好用，wa了两次。
#include <stdio.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#define LL long long
#define _LL __int64
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 110;int n,m;
int inter[maxn];
int Map[maxn][maxn];
int dis[maxn],vis[maxn];
int pre[maxn];void debug()
{for(int i = 1; i <= n+1; i++){for(int j = 1; j <= n+1; j++)printf("%d ",Map[i][j]);printf("\n");}
}void spfa()
{queue <int> que;memset(vis,0,sizeof(vis));memset(dis,-INF,sizeof(dis));memset(pre,-1,sizeof(pre));dis[1] = 0;vis[1] = 1;que.push(1);while(!que.empty()){int u = que.front();que.pop();vis[u] = 0;for(int v = 1; v <= n+1; v++){if(Map[u][v] >= 0&& dis[v] < dis[u] + Map[u][v]){dis[v] = Map[u][v] + dis[u];pre[v] = u;if(!vis[v]){vis[v] = 1;que.push(v);}}}}
}void output()
{int t = n+1;int ans[maxn];int cnt = 0;while(pre[t] != -1){ans[cnt++] = t;t = pre[t];}printf("1");for(int i = cnt-1; i >= 1; i--)printf("->%d",ans[i]);printf("->1\n");
}int main()
{int test;int u,v;scanf("%d",&test);for(int item = 1; item <= test; item++){if(item != 1)printf("\n");scanf("%d",&n);for(int i = 1; i <= n; i++)scanf("%d",&inter[i]);inter[n+1] = 0;memset(Map,-1,sizeof(Map));scanf("%d",&m);while(m--){scanf("%d %d",&u,&v);Map[u][v] = inter[v];}spfa();printf("CASE %d#\n",item);printf("points : %d\n",dis[n+1]);printf("circuit : ");output();}return 0;}求最长路有点像最长上升子序列，再拿最长上升子序列水一水。
#include <stdio.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#define LL long long
#define _LL __int64
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 110;int n,m;
int inter[maxn];
int Map[maxn][maxn];
int dis[maxn],vis[maxn];
int pre[maxn];
int dp[maxn];void solve()
{memset(pre,-1,sizeof(pre));for(int i = 1; i <= n+1; i++){dp[i] = inter[i];for(int j = 1; j < i; j++){if( Map[j][i] >= 0 && dp[i] < dp[j] + Map[j][i]){dp[i] = dp[j] + Map[j][i];pre[i] = j;}}}printf("points : %d\n",dp[n+1]);printf("circuit : ");int ans[maxn],cnt = 0;int t = n+1;while(t != -1){ans[cnt++] = t;t = pre[t];}ans[cnt] = 1;for(int i = cnt; i >= 1; i--)printf("%d->",ans[i]);printf("%d\n",1);
}int main()
{int test;int u,v;scanf("%d",&test);for(int item = 1; item <= test; item++){if(item != 1)printf("\n");scanf("%d",&n);for(int i = 1; i <= n; i++)scanf("%d",&inter[i]);inter[n+1] = 0;memset(Map,-1,sizeof(Map));scanf("%d",&m);while(m--){scanf("%d %d",&u,&v);Map[u][v] = inter[v];}printf("CASE %d#\n",item);solve();}return 0;
}
这篇关于hdu 1224 Free DIY Tour(最长路/dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
