学步园

题目链接:   uva
10000

题目大意:   无环的有向连通图中

                  从某点出发可以达到的最远的点

                  并且输出长度和终点编号

解题思路:   求某点出发的最长路径

                  BFS从起点开始搜索，dist[ ]存储到达该点时的最长距离：

                  1.如果这个点没被访问过，则访问，并更新dist[ ]

                  2.如果访问这个时路径长度大于之前访问它最长的路径，则访问，并更新dist[ ]

                  第二点可行的条件在于任何顶点被访问到的最长距离有上限(因为没有环)

                  SPFA在搜索中可以使用的两种情况: 

                  1.任意顶点被访问到的最短距离有下限(无负权值环)，用来求最短路

                  2.任意顶点被访问到的最长路径有下限(无环)，用来求最长路

PS：注意BFS不要重复入队列，要用visit[ ]标记

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#define MAX 200
using namespace std;
int visit1[MAX],edge[MAX][MAX],n;
int dist[MAX];

void SPFA(int u)
{
	int vv,s,i,e,list[MAX*MAX];
	memset(visit1,0,sizeof(visit1));
	s=e=0;                  //
	list[s++]=u;            //初始化队列
	dist[u]=0;
	visit1[u]=1;
	while(e!=s)
	{
		vv=list[e++];
		visit1[vv]=0;                    //*出队列清除
		for(i=1;i<=n;i++)
		{
			if(edge[vv][i]==1&&dist[vv]+1>dist[i])  //**如果这条边存在并且这条路径比之前的大
			{
				dist[i]=dist[vv]+1;
				if(!visit1[i])           //**BFS最容易错的地方，不要重复入队列
				{
					list[s++]=i; 
					visit1[i]=1;         //*入队列标记
				}
			}
		}
	}
}

int main()
{
	int i,Star,a,b,t=0,flag;
	int mmax;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)
			break;
		t++;
		memset(edge,0,sizeof(edge));
		memset(dist,0,sizeof(dist));
		scanf("%d",&Star);               //记录起点
		while(scanf("%d%d",&a,&b))
		{
			if(a==0&&b==0)
				break;
			edge[a][b]=1;                //有向图
		}
		flag=Star,mmax=0;
		SPFA(Star);                       //开始搜索
		for(i=1;i<=n;i++)
		{
			if(mmax<dist[i])
            mmax=dist[i];
		}
		for(i=n;i>=1;i--)
		{
			if(mmax==dist[i])
				flag=i;
		}
		printf("Case %d: The longest path from %d has length %d, finishing at %d.",t,Star,mmax,flag);
		printf("\n\n");
	}
	return 0;
}