最短路

Floyd

三方，顺序是 \(k,i,j\)，理由是我们定义的数组 f[k][x][y]，表示只允许经过结点 \(1\) 到 \(k\)（也就是说，在子图 \(V'={1, 2, \ldots, k}\) 中的路径，注意，\(x\) 与 \(y\) 不一定在这个子图中），结点 \(x\) 到结点 \(y\) 的最短路长度，可以压掉一维。

for (int k = 1; k <= n; k++)
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			f[i][j] = min(f[i][j], f[i][k] + f[k][j]);

P6175 正权无向图最小环

在递推 Floyd 的时候，顺便枚举了两个点和其中继点。我们就可以把 \(dis(i,j),(i,k),(k,j)\) 共同构成的环更新答案。我们知道，\(dis(i,j)\) 一定是只经过前 \(k\) 个点的条件下最小的（尽管可能不止一条边连接），所以这是当前 \((i,k,j)\) 环的最小答案。

for (int k = 1; k <= n; k++)
{
	/*
	i = j 是无意义的
	i = k 或 j = k 也是无意义的
	*/
	for (int i = 1; i <= k - 1; i++)
	{
		for (int j = i + 1; j <= k - 1; j++)
			ans = min(ans, dis[i][j] + a[i][k] + a[k][j]);
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
			dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
	}
}

B3611 【模板】传递闭包

给定无向图邻接矩阵，求出传递闭包。

传递闭包：表示两点间是否能通达。

也使用 Floyd，只不过 min 变成了 1/0 问题。

// 这样做是显然的
for (int k = 1; k <= n; k++)
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			dis[i][j] = (dis[i][j] || (dis[i][k] && dis[k][j]));

也可以用 Bitset 优化到 \(O(\frac{n^3}{w})\)。

bitset<maxn> a[maxn];
for (int k = 1; k <= n; k++)
{
	for (int i = 1; i <= n; i++)
	{
		if (a[i][k])	  // 若 i k 连通
			a[i] |= a[k]; // i 也能到 k 能到的点
	}
}