boj 1071

Description
dalong他们马上要去final了，他们这次将要坐灰机到瑞典，灰机会经过N个城市（包括起点和终点），由于这次出国机会难得，他们决定的要访问尽可能多的城市。注意这是一张往返机票，并且每个城市最多只能访问一次，除了起始点可以访问两次。现在给出N个城市，编号从1到N，并且城市从东往西排列。去时飞机只能从东往西飞不能反过来，回来时，只能从西往东不能反过来。注意必须到达最西面才能开始返回！现在会给出M条航班，航班都是双向的。由于dalong们最近非常忙，要wangkun帮他们计划如何安排使飞机可以往返并且访问尽可能的城市。wangkun最近有点脑残，聪明的你，能不能帮一下wangkun呢？


Input
输入两个整数 N ， M （2<=N<=100）(0<=M<=5000)
下面是M行，每行两个整数a ，b，表示城市a和城市b之间有一条航线。
以 0 0 结束。

Output
如果存在往返路线则输出最多访问城市数，
否则输出No solution


Sample Input

4 4
1 2
2 4
3 4
1 3
0 0


Sample Output

4

 

第一次错误的想法（脑残）：

假设存在一条往返路径，且为经过城市最多的路径(1,a1,a2,...,ax,n,by,...,b2,b1,1),则R1：(1,a1,a2,...ax,n)和R2：(1,b1,b2,...by,n)中肯定有一条是从1到n经过城市最多的路径。因为假设不是，存在另外一条路径R3：(1,c1,c2,...,cz,n)为经过城市最多的路径，则R1和R3肯定有交集(如果不存在，则R3可以替换R2，构成一条经过城市更多的路径)，同理可得R2和R3肯定也有交集，推出R1和R2有交集，与题意每个城市只经过一次相悖，所以R1和R2中肯定有一条是从1到n经过城市最多的路径。

 以上证明中忽略了一点就是，R1和R2的交集如果就是1和n的话，证明就是错误的，反例：

R1：(1,2,4)
R2：(1,3,4)
R3：(1,2,3,4)

 因为错误的想法，导致用dp[i]记录1到i经过最多城市的个数，并用path[][]记录路径，然后对于经过城市最多路径的集合X，从中选出一条路径，去除经过的城市，然后再次dp求出返回路径，相加得到结果，错误代码：

#include<iostream>
using namespace std;

#define N 106

bool Graph[N][N];
bool flag[N];
int dp1[N];
int dp2[N];
int path[N][N];
int back;

void find(int i,int n)
{
	if(i>1)
	{
		for(int j=1;j<path[i][0];j++)
		{
			Graph[i][path[i][j]]=false;
			Graph[path[i][j]][i]=false;
			flag[path[i][j]]=true;
			find(path[i][j],n);
			Graph[i][path[i][j]]=true;
			Graph[path[i][j]][i]=true;
			flag[path[i][j]]=false;
		}
	}
	else if(i==1)
	{
		dp2[1]=1;
		flag[1]=false;
		for(int p=2;p<=n;p++)
		{
			dp2[p]=0;
			if(flag[p]==false)
			{
				for(int j=1;j<p;j++)
				{
					if(flag[j]==false&&Graph[j][p]&&dp2[j]&&dp2[p]<dp2[j]+1)
						dp2[p]=dp2[j]+1;
				}
			}
		}
		dp2[n]>back?back=dp2[n]:back;
	}
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	while(!(n==0&&m==0))
	{
		for(int i=1;i<=n;i++)
		{
			flag[i]=false;
			dp1[i]=dp2[i]=0;
			for(int j=1;j<=n;j++)
			{
				Graph[i][j]=0;
				path[i][j]=0;
			}
		}
		for(int i=0;i<m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			Graph[a][b]=true;
			Graph[b][a]=true;
		}
		dp1[1]=1;
		for(int i=2;i<=n;i++)
		{
			int cnt=1;
			for(int j=1;j<i;j++)
			{
				if(Graph[j][i]&&dp1[j])
				{
					if(dp1[i]<dp1[j]+1)
					{
						dp1[i]=dp1[j]+1;
						cnt=1;
						path[i][cnt++]=j;
					}
					else if(dp1[i]==dp1[j]+1)
						path[i][cnt++]=j;
				}
			}
			path[i][0]=cnt;
		}
		if(path[n][0]==0)
			printf("No solution\n");
		else
		{
			back=0;
			find(n,n);
			if(back==0)
				printf("No solution\n");
			else printf("%d\n",dp1[n]+back-2);
		}
		scanf("%d%d",&n,&m);
	}
}

 正确的解法：dp[i][j]记录从i经过n到达j的最多城市个数

代码：

#include<iostream>
using namespace std;

#define N 106

bool Graph[N][N];
int dp[N][N];

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	while(!(n==0&&m==0))
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				Graph[i][j]=0;
				dp[i][j]=0;
			}
		}
		for(int i=0;i<m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			Graph[a][b]=true;
			Graph[b][a]=true;
		}
		dp[n][n]=1;
		for(int i=n;i>=1;i--)
		{
			for(int j=i-1;j>=1;j--)
			{
				for(int k=j+1;k<=n;k++)
				{
					if(Graph[j][k]&&dp[i][k]&&dp[i][j]<dp[i][k]+1)
						dp[j][i]=dp[i][j]=dp[i][k]+1;
				}
			}
		}
		int p=1;
		for(int i=2;i<=n;i++)
			if(Graph[1][i]&&dp[i][1]>dp[p][1])
				p=i;
		if(Graph[1][p]&&dp[1][p]>2)//每条航班只能一次，去除1到n存在直接路径Graph[1][n]
			printf("%d\n",dp[1][p]);
		else
			printf("No solution\n");
		scanf("%d%d",&n,&m);
	}
}

 

想问题总是容易钻到死胡同里，推理的时候不够细心，以后分析的时候应该专心点，细致点!!!