学步园

判断最长路径是否成环。

我用的是暴力，把所有的点当作起始点枚举一次，用bellmanford判断是否成环即可。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
struct n1
{
	int s,e;
	double w;
};
n1 path[1000];
bool ishuan(int s,double sw,int v,int e)
{
	bool flag;
	int i;
	double d[31];
	for(i=1;i<=v;i++)
	{
		d[i]=0;
	}
	d[s]=sw;
	while(v--)
	{
		flag=1;
		for(i=1;i<=e;i++)
		{
			if(d[path[i].e]<d[path[i].s]*path[i].w)
			{
				flag=0;
				d[path[i].e]=d[path[i].s]*path[i].w;
			}
		}
		if(flag)
		return 0;
	}
	return 1;
}
int main()
{
	bool flag;
	double ex;
	int n,m,i,j,index1,index2,lizi;
	char name[31][100],temp1[100],temp2[100];
	lizi=0;
	while(scanf("%d",&n)&&n!=0)
	{
		lizi++;
		for(i=1;i<=n;i++)
		{
			scanf("%s",name[i]);
		}
		scanf("%d",&m);
		for(j=1;j<=m;j++)
		{
			scanf("%s%lf%s",temp1,&ex,temp2);
			index1=index2=0;
			for(i=1;index1==0||index2==0;i++)
			{
				if(strcmp(name[i],temp1)==0)
				{
					index1=i;
				}
				if(strcmp(name[i],temp2)==0)
				{
					index2=i;
				}
			}
			path[j].s=index1;
			path[j].e=index2;
			path[j].w=ex;
		}
		flag=0;
		for(i=1;i<=n;i++)
		{
			if(ishuan(i,1.0,n,m))
			{
				flag=1;
				break;
			}
		}
		printf("Case %d: ",lizi);
		if(flag)
		{
			printf("Yes\n");
		}
		else
		{
			printf("No\n");
		}
	}
}