Algorithm

USACO Section5.4 Canada Tour (tour)

Problem Summary

Given a graph with vertices 1,2,…,N and M undirected edges, find the maximal length of a round trip.

The tour should have two parts. Let the first part be A[1]->A[2]->…->A[K], the second be B[1]->B[2]->…->B[P]. They should satisfy:

  1. A[1]=B[P]=1, A[K]=B[1]=N.
  2. The two parts have no common vertices except 1 and N, i.e. A[i]!=B[j], for any 1<i<K, 1<j<P.
  3. A[i]<A[j], for any 1<=i<j<=K
  4. B[i]>B[j], for any 1<=i<j<=P

Solution

Since array A is strictly increasing and array B is strictly decreasing, we can use dynamic programming.
We can split the round tour into 2 seperate tours for 2 people.
Let f[i][j] be the maximal number of vertices visited when one person is at vertex i, and the other is at j. The DP equtions are:

1
2
3
f[1][1]=1;
f[i][j]=max{f[i][k]}+1, if 1<=i<j<=n && 1<=k<j &&  map[j][k]==true && f[i][k]!=0
f[j][i]=f[i][j],1<=i<j<=n

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
const int maxn = 102;
int n,m;
char city[maxn][20];
bool g[maxn][maxn];
int f[maxn][maxn];
int get_id(char *s)
{
	for(int i=1;i<=n;i++)
		if(strcmp(s,city[i])==0)
			return i;
	return 0;
}
int main()
{
	fstream fin("tour.in",ios::in);
	fstream fout("tour.out",ios::out);
	fin>>n>>m;
	for(int i=1;i<=n;i++)
		fin>>city[i];
	int x,y;
	char st[20],en[20];
	for(int i=0;i<m;i++)
	{
		fin>>st>>en;
		x=get_id(st);
		y=get_id(en);
		if(x<y) g[x][y]=true;
		else g[y][x]=true;
	}
	f[1][1]=1;
	int ans=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			for(int k=1;k<j;k++)
				if(g[k][j])
				{
					if(k==i && i!=1) continue;
					if(f[i][k]>0 && f[i][k]+1>f[i][j])
						f[i][j]=f[i][k]+1;
				}
			f[j][i]=f[i][j];
		}
		if(i==n)
		{
			if(f[n][n]-1>ans)
				ans=f[n][n]-1;
		}
		else
		if(g[i][n] && f[i][n]>ans)
			ans=f[i][n];
	}
	
	fout<<ans<<endl;
	fin.close();
	fout.close();
	return 0;
}