P1359 租用游艇【Floyd】

为什么我想讲Floyd算法呢？

因为我觉得 我自己掌握的不太好 码量很少

好，让我们回顾一下Floyd算法

Floyd算法
Floyd算法（Floyd-Warshall algorithm）又称为弗洛伊德算法、插点法，是解决给定 的加权图中顶点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问 题，同时也被用于计算有向图的传递闭包。该算法名称以创始人之一、1978年图灵奖获 得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
（概念太麻烦了，懒得打，我就直接复制了）

适用范围：无负权回路即可，边权可正可负，运行一次算法即可求得任意两点间最短路。

时间复杂度 ： O (n * n * n)

这个算法的具体步骤是：

1、初始化过程：将邻接矩阵copy到二维数组A中，将二维数组Path中所有元素填充为-1(都没有开

始寻找，哪里来的中间顶点呢)。

 2、列出顶点的所有可能二元组，自己到自己不算。

 3、选择编号为0的点为中间点，从 2.中二元组集合的第一个元素开始，执行以下过程

       3.1：用i，j两个变量分别指向二元组里的两个元素，比如{0，1}这个二元组，i指向0；j指向1

       3.2：判断A[i][j] > A[i][0] + A[0][j]吗？如果表达式为真，进入3.3；若为假，则结束本次过程，进入下一个二元组

       3.3：更新A[i][j]的值为A[i][0] + A[0][j]，Path[i][j]的值为0

   4、重复步骤 3，直到所有的顶点都做过一次中间点为止。

所以，Floyd的核心代码是

 

--->                                                                                                                                               <---

for(int k=1;k<=n;k++)//连接点
	for(int i=1;i<=n;i++)//起点
	    for(int j=1;j<=n;j++)
        {//终点
		    
	    }

--->                                                                                                                                               <---

现在来康康这道题

我们就有了这么一个：

min (到i站时的最少租金，到j站时的最少租金 + j到i站的租金)

代码写出来就是：

--->                                                                                                                                               <---

if (Floyd[i][k] + Floyd[k][j] < Floyd[i][j])
					Floyd[i][j] = Floyd[i][k] + Floyd[k][j];

 

--->                                                                                                                                               <---

但是

细节 细节 细节

题中说:游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇

意思就是：游艇只会往下游走，而不会向上走

So，

枚举中间点在i游艇的上游，直接跳过 

--->                                                                                                                                               <---

if (k <= i) continue;

--->                                                                                                                                               <---

根据题意，我们可以知道，我们要求的就是游艇1到游艇n的距离，也就是a[1][n]

最后输出就完事了

AC CODE：

--->                                                                                                                                               <---

#include 
using namespace std;
const int N = 202;
int n;
int Floyd[N][N];
int main ()
{
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		for (int j = i + 1; j <= n; j++)
		{
			cin >> Floyd[i][j];
		}
	}
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = i + 1; j <= n; j++)
			{
				if (k <= i) continue;//枚举中间点在i的上游，直接跳过 
				if (Floyd[i][k] + Floyd[k][j] < Floyd[i][j])
					Floyd[i][j] = Floyd[i][k] + Floyd[k][j];
			}
		}
	}
	cout << Floyd[1][n] << endl;
	return 0;
}

--->                                                                                                                                               <---

Good bye