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("
");
	}
}

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
");
}

int main()
{
	int test;
	int u,v;
	scanf("%d",&test);
	for(int item = 1; item <= test; item++)
	{
		if(item != 1)
			printf("
");

		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#
",item);
		printf("points : %d
",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
",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
",1);
}

int main()
{
	int test;
	int u,v;
	scanf("%d",&test);
	for(int item = 1; item <= test; item++)
	{
		if(item != 1)
			printf("
");

		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#
",item);
		solve();
	}
	return 0;
}