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;

}