hdoj1599

这几天狂刷webdiy,做了很多题目却来不及发上来总结,不多很多都是以前知识点的复习,今天学了最小环。这个写一下重点。
floyd求最小环关键代码

for(k=1;k<=n;k++)
{
////////////////////////////////////////////////////////////////////////
	for(i=1;i<=k-1;i++)
		for(j=i+1;j<=k-1;j++)
			if(map[k][i]+dist[i][j]+map[j][k]<ans)
				ans=map[k][i]+dist[i][j]+map[j][k];
/////////////////////////////////////////////////////////////////////////
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			if(dist[i][k]+dist[k][j]<dist[i][j])
				dist[i][j]=dist[i][k]+dist[k][j];
		}
}

可见,与普通floyd的唯一不同点就是斜线包含部分。以下称这部分代码为*代码
map[k][i]+dist[i][j]+map[j][k]代码求的是以k为环中最大编号的环的长度,其中i与j是与k点直接相连的点(这里没有判断i、j是否直接与k相邻,但可以保证正确,因为不相邻的点之间距离为inf,加起来之后肯定不是最小环,对结果无影响)。
为什么*代码要放在在前面
当要执行*代码时最外层循环已经执行了k-1次,这表示对于图中任意两点i、j,已经在它们之间插入了1——k-1这些点(用1——k-1这些点松弛过),所以此时任意两点i、j之间的最短路只可能经过了1——k-1这些点,不会经过k点,这样就保证了map[k][i]-dist[i][j]-map[j][k]形成的是环,也就是说没有重复经过同一点。
为什么*代码中i、j两层循环中i、j的范围是比k小?
因为已经约定*代码找的是以k为环中编号最大点的环的长度,按我的理解,其实这两层循环也可以写成
for(i=1;i<=m;i++){for(j=1;j<=n;j++){;}}
但是这样会重复计算很多环,大大降低了时间效率。

如果允许来回的路上经过重复点,并且没有必须经过两个不同点的限制,求指定的一个源点到任意点再回到源点的最短距离,可以怎么做?

答:可以用两次dij搞定,两次都是求出源点到任意点的最短路,只是第二次对应的图是原图的边方向反一下。
很显然,边反一下之后求出s到t的最短路其实是从t到s的最短路径。

#include<stdio.h>
#include<stdlib.h>
#define inf 10000000
#define maxn 110
int dist[maxn][maxn];
int map[maxn][maxn];
int main()
{
	int n,m;
	int i,j,k;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(i==j)
				{
					map[i][j]=dist[i][j]=0;
				}
				else
				{
					map[i][j]=dist[i][j]=inf;
				}
		int a,b,c;
		for(i=1;i<=m;i++)
		{
			scanf("%d %d %d",&a,&b,&c);
			if(c<dist[a][b])
			{
				map[a][b]=map[b][a]=dist[a][b]=dist[b][a]=c;
			}
		}
		int ans=inf;
		for(k=1;k<=n;k++)
		{
			for(i=1;i<=k-1;i++)
				for(j=i+1;j<=k-1;j++)
					if(map[k][i]+dist[i][j]+map[j][k]<ans)
						ans=map[k][i]+dist[i][j]+map[j][k];
			for(i=1;i<=n;i++)
				for(j=1;j<=n;j++)
				{
					if(dist[i][k]+dist[k][j]<dist[i][j])
						dist[i][j]=dist[i][k]+dist[k][j];
				}
		}

		
		if(ans>=inf)
			printf("It's impossible.\n");
		else
			printf("%d\n",ans);
	
	
	
	}

//system("pause");
return 0;
}