Home > Old Blog Posts > USACO 5.4.2 Canada Tour

USACO 5.4.2 Canada Tour


我看到这题就立马傻眼了,以下是自己对Nocow上题解的理解
这题的叙述(纯指叙述)有些类似于NOIP2008提高组第3题传纸条,都是兜一圈再回来,我们可以用类似的方法,将求一条回路转化为求两条不相交的路径(两个人分别从最西边的城市出发,到达最东边的城市的路径)
设状态f[i][j]表示第一个人已经走到第i个城市,第二个人走到第j个城市时所访问的城市数目的最大值,则
f[i][j]=max{f[i][k]+1} (link[k][j]&&f[i][k]>0)
+1写在max里是因为如果没有满足条件的k的话,f[i][j]=0
另外,显然有f[i][j]=f[j][i]
最终的结果就是max{f[N][i]} (link[i][N])

/*
ID: dementr1
PROG: tour
LANG: C++
*/
#include
#include
using namespace std;
ifstream fin("tour.in");
ofstream fout("tour.out");
int n;
string name[101];
bool v[101][101]={false};
int ans=-1;
int f[101][101]={};
int search(string s)
{
	for(int i=1;i>n>>num;
	for(int i=1;i>name[i];
	for(int i=0;i>tmp1>>tmp2;
		from=search(tmp1);
		to=search(tmp2);
		v[from][to]=v[to][from]=true;
	}
	fin.close();
}
void work()
{
	f[1][1]=1;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(i!=1||j!=1&&f[i][j]==0)
			{
				int max=-1;
				for(int k=1;k0)
						if(f[i][k]+1>max)
							max=f[i][k]+1;
				f[i][j]=f[j][i]=max;
			}
	for(int i=1;ians)
			ans=f[i][n];
}
void print()
{
	if(ans<=1)
		fout<<1<<endl;
	else
		fout<<ans<<endl;
}
int main()
{
	init();
	work();
	print();
	return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: