Floyd

任意两点之间的最短路

做n次 dijkstra 时间复杂度是 O(m log n) * n

Floyd 时间复杂度是 $O(n^3)$

如果边数超过 $m >= n^2 / \log n$ 那么 floyd 更快

本质思路是动态规划，用f[k][i][j]表示除了起点和终点，只允许经过标号小于等于k的节点，从i到j的最短路。
初始f[0][i][j]取决于i到j的最短边。
转移方程

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

实际上第一维可以省略

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

不要记错循环的顺序，先枚举中间点。
Floyd还可以用于计算传递闭包和无向图最小环，是一个值得记住的算法。

所以 Floyd 适合在完全图上使用

完全图：任意两个点之间都有边

https://en.wikipedia.org/wiki/Floyd–Warshall_algorithm

Dynamic Programming
动态规划的思路

d[i][j][k] means from i to j, we can only use intermediate vertices <= k,
the length the shortest path
d[i][j][k] 表示从 i 到 j 除了起点和终点之外，只能经过标号 <= k 的点

d[i][j][0] input graph
d[i][j][0] 输入的图，不能经过任何中间点

d[i][j][n] output
d[i][j][n] 输出的图，可以经过任何中间点

d[i][j][k] = min(d[i][j][k-1], d[i][k][k-1] + d[k][j][k-1])

读入 邻接矩阵
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        cin >> d[i][j];
    }
}

读入边
for (int i = 0; i < m; i++)
{
    cin >> x >> y >> z;
    d[x][y] = min(d[x][y], z);
    // 可能有重边
}

// 首先枚举中间点 k
for (int k = 0; k < n; k++) 
{
    // 枚举起点i
    for (int i = 0; i < n; i++)
    {
        // 枚举终点j
        for (int j = 0; j < n; j++)
        {
            // i 和 j 的循环可以交换
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            // d[i][j][k] = min(d[i][j][k-1], d[i][k][k-1] + d[k][j][k-1])
            // 实际实现中并不会用三维数组，会用二维数组
        }
    }
}

Floyd算法的应用

无向图最小环
用 bitset 做传递闭包

参考题目

P2910 [USACO08OPEN]Clear And Present Danger S

https://www.luogu.com.cn/problem/P2910

题目描述

Farmer John is on a boat seeking fabled treasure on one of the N (1 <= N <= 100) islands conveniently labeled 1..N in the Cowribbean Sea.

The treasure map tells him that he must travel through a certain sequence A_1, A_2, ..., A_M of M (2 <= M <= 10,000) islands, starting on island 1 and ending on island N before the treasure will appear to him. He can visit these and other islands out of order and even more than once, but his trip must include the A_i sequence in the order specified by the map.

FJ wants to avoid pirates and knows the pirate-danger rating (0 <= danger <= 100,000) between each pair of islands. The total danger rating of his mission is the sum of the danger ratings of all the paths he traverses.

Help Farmer John find the least dangerous route to the treasure that satisfies the treasure map's requirement.

输入格式

* Line 1: Two space-separated integers: N and M

* Lines 2..M+1: Line i+1 describes the i_th island FJ must visit with a single integer: A_i

* Lines M+2..N+M+1: Line i+M+1 contains N space-separated integers that are the respective danger rating of the path between island i and islands 1, 2, ..., and N, respectively. The ith integer is always zero.

输出格式

* Line 1: The minimum danger that Farmer John can encounter while obtaining the treasure.

样例 #1

样例输入 #1

样例输出 #1

提示

There are 3 islands and the treasure map requires Farmer John to visit a sequence of 4 islands in order: island 1, island 2, island 1 again, and finally island 3. The danger ratings of the paths are given: the paths (1, 2); (2, 3); (3, 1) and the reverse paths have danger ratings of 5, 2, and 1, respectively.

He can get the treasure with a total danger of 7 by traveling in the sequence of islands 1, 3, 2, 3, 1, and 3. The cow map's requirement (1, 2, 1, and 3) is satisfied by this route. We avoid the path between islands 1 and 2 because it has a large danger rating.

输入输出格式

输入格式：

第一行：两个用空格隔开的正整数N和M

第二到第M+1行：第i+1行用一个整数Ai表示FJ必须经过的第i个岛屿

第M+2到第N+M+1行：第i+M+1行包含N个用空格隔开的非负整数分别表示i号小岛到第1...N号小岛的航线各自的危险指数。保证第i个数是0。

输出格式

第一行：FJ在找到宝藏的前提下经过的航线的危险指数之和的最小值。

说明

这组数据中有三个岛屿，藏宝图要求FJ按顺序经过四个岛屿：1号岛屿、2号岛屿、回到1号岛屿、最后到3号岛屿。每条航线的危险指数也给出了：航路(1，2)、(2，3)、(3，1)和它们的反向路径的危险指数分别是5、2、1。

FJ可以通过依次经过1、3、2、3、1、3号岛屿以7的最小总危险指数获得宝藏。这条道路满足了奶牛地图的要求（1，2，1，3）。我们避开了1号和2号岛屿之间的航线，因为它的危险指数太大了。

注意：测试数据中a到b的危险指数不一定等于b到a的危险指数！

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, ans;
int a[10020];
int d[120][120];
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> d[i][j];
		}
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	for (int i = 1; i < m; i++) {
		ans += d[a[i - 1]][a[i]];
	}
	cout << ans << endl;
}

题解

CF25C Roads in Berland

https://codeforces.com/problemset/problem/25/C
https://www.luogu.com.cn/problem/CF25C

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, z;
int d[320][320];
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> d[i][j];
		}
	}
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	cin >> m;
	for (int k = 0; k < m; k++)
	{
		cin >> x >> y >> z;
		d[x][y] = min(d[x][y], z);
		d[y][x] = min(d[y][x], z);
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				d[i][j] = min(d[i][j], d[i][x] + d[x][j]);
			}
		}
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				d[i][j] = min(d[i][j], d[i][y] + d[y][j]);
			}
		}
		long long z = 0;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j < i; j++)
			{
				z += d[i][j];
			}
		}
		cout << z << " ";
	}
	return 0;
}

题解

P6175 无向图的最小环问题

https://www.luogu.com.cn/problem/P6175

题目描述

给定一张无向图，求图中一个至少包含 $3$ 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中，你需要输出最小的环的边权和。若无解，输出 No solution.。

输入格式

第一行两个正整数 $n,m$ 表示点数和边数。

接下来 $m$ 行，每行三个正整数 $u,v,d$ ，表示节点 $u,v$ 之间有一条长度为 $d$ 的边。

输出格式

输出边权和最小的环的边权和。若无解，输出 No solution.。

样例 #1

样例输入 #1

样例输出 #1

提示

样例解释：一种可行的方案： $1-3-5-2-1$ 。

对于 $20\%$ 的数据， $n,m \leq 10$ 。

对于 $60\%$ 的数据， $m\leq 100$ 。

对于 $100\%$ 的数据， $1\le n\leq 100$ ， $1\le m\leq 5\times 10^3$ ， $1 \leq d \leq 10^5$ 。

无解输出包括句号。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[120][120];
int d[120][120];
int main() {
	cin >> n >> m;
	memset(a, 0x1f, sizeof a);
	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		a[x][y] = min(a[x][y], z);
		a[y][x] = min(a[y][x], z);
	}
	int ans = 0x1f1f1f1f;
	memcpy(d, a, sizeof d);
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i < k; i++) {
			for (int j = 1; j < i; j++) {
				ans = min(ans, a[i][k] + a[k][j] + d[i][j]);
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	if (ans == 0x1f1f1f1f) {
		printf("No solution.\n");
	} else {
		printf("%d\n", ans);
	}
	return 0;
}

题解

最小环上至少三个点，并且不能有重复的点（当然也没有重复的边）
枚举k点是最小环中标号最大的的节点
k is largest vertex in the cycle
(u --- k --- v --- .... --- u)

假设 k 两边点是 u 和 v
那么从 v 到 u 找一条只允许只用标号 <= k-1 的最短路

u到k的边 k到v的边 v到u的路径构成一个环，用这个环更新答案
use a[u][k] + a[k][v] + d[v][u][k-1] to update the answer

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[120][120];
int d[120][120];
int main() {
    cin >> n >> m;
    memset(a, 0x1f, sizeof a);
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        a[x][y] = min(a[x][y], z);
        a[y][x] = min(a[y][x], z);
    }
    int ans = 0x1f1f1f1f;
    memcpy(d, a, sizeof d);
    for (int k = 1; k <= n; k++) {
        // 环上最大的点是k，和k相邻的两个点是i和j
        for (int i = 1; i < k; i++) {
            for (int j = 1; j < i; j++) {
                ans = min(ans, a[i][k] + a[k][j] + d[i][j]);
                // d[i][j]存的最短路是 从i到j，只能经过标号<k的点的最短路
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    // 如果找不到有意义的答案就是无解
    if (ans == 0x1f1f1f1f) {
        printf("No solution.\n");
    } else {
        printf("%d\n", ans);
    }
    return 0;
}

P1119 灾后重建

https://www.luogu.com.cn/problem/P1119

题目背景

B 地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通车，只能到达重建完成的村庄。

题目描述

给出 B 地区的村庄数 $N$ ，村庄编号从 $0$ 到 $N-1$ ，和所有 $M$ 条公路的长度，公路是双向的。并给出第 $i$ 个村庄重建完成的时间 $t_i$ ，你可以认为是同时开始重建并在第 $t_i$ 天重建完成，并且在当天即可通车。若 $t_i$ 为 $0$ 则说明地震未对此地区造成损坏，一开始就可以通车。之后有 $Q$ 个询问 $(x,y,t)$ ，对于每个询问你要回答在第 $t$ 天，从村庄 $x$ 到村庄 $y$ 的最短路径长度为多少。如果无法找到从 $x$ 村庄到 $y$ 村庄的路径，经过若干个已重建完成的村庄，或者村庄 $x$ 或村庄 $y$ 在第 $t$ 天仍未重建完成，则需要返回 -1。

输入格式

第一行包含两个正整数 $N,M$ ，表示了村庄的数目与公路的数量。

第二行包含 $N$ 个非负整数 $t_0, t_1,…, t_{N-1}$ ，表示了每个村庄重建完成的时间，数据保证了 $t_0 ≤ t_1 ≤ … ≤ t_{N-1}$ 。

接下来 $M$ 行，每行 $3$ 个非负整数 $i, j, w$ ， $w$ 为不超过 $10000$ 的正整数，表示了有一条连接村庄 $i$ 与村庄 $j$ 的道路，长度为 $w$ ，保证 $i≠j$ ，且对于任意一对村庄只会存在一条道路。

接下来一行也就是 $M+3$ 行包含一个正整数 $Q$ ，表示 $Q$ 个询问。

接下来 $Q$ 行，每行 $3$ 个非负整数 $x, y, t$ ，询问在第 $t$ 天，从村庄 $x$ 到村庄 $y$ 的最短路径长度为多少，数据保证了 $t$ 是不下降的。

输出格式

共 $Q$ 行，对每一个询问 $(x, y, t)$ 输出对应的答案，即在第 $t$ 天，从村庄 $x$ 到村庄 $y$ 的最短路径长度为多少。如果在第t天无法找到从 $x$ 村庄到 $y$ 村庄的路径，经过若干个已重建完成的村庄，或者村庄x或村庄 $y$ 在第 $t$ 天仍未修复完成，则输出 $-1$ 。

样例 #1

样例输入 #1

样例输出 #1

-1
-1
5
4

提示

对于 $30\%$ 的数据，有 $N≤50$ ；

对于 $30\%$ 的数据，有 $t_i= 0$ ，其中有 $20\%$ 的数据有 $t_i = 0$ 且 $N>50$ ；

对于 $50\%$ 的数据，有 $Q≤100$ ；

对于 $100\%$ 的数据，有 $N≤200$ ， $M≤N \times (N-1)/2$ ， $Q≤50000$ ，所有输入数据涉及整数均不超过 $100000$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, q;
int t[220];
int d[220][220];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &t[i]);
	}
	memset(d, 0x3f, sizeof d);
	for (int i = 0; i < n; i++)
	{
		d[i][i] = 0;
	}
	for (int i = 0; i < m; i++)
	{
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		d[x][y] = z;
		d[y][x] = z;
	}
	scanf("%d", &q);
	for (int l = 0, k = 0; l < q; l++)
	{
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		for (; k < n && t[k] <= z; k++)
		{
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
				}
			}
		}
		if (t[x] <= z && t[y] <= z && d[x][y] < 0x3f3f3f3f)
		{
			printf("%d\n", d[x][y]);
		}
		else
		{
			printf("%d\n", -1);
		}
	}
	return 0;
}

题解

P4306 [JSOI2010]连通数

https://www.luogu.com.cn/problem/P4306

题目背景

本题数据过水，可前往 https://www.luogu.com.cn/problem/U143178 提交

题目描述

度量一个有向图连通情况的一个指标是连通数，指图中可达顶点对个的个数。

如图

qwq

顶点 $1$ 可达 $1, 2, 3, 4, 5$

顶点 $2$ 可达 $2, 3, 4, 5$

顶点 $3$ 可达 $3, 4, 5$

顶点 $4, 5$ 都只能到达自身。

所以这张图的连通数为 $14$ 。

给定一张图，请你求出它的连通数

输入格式

输入数据第一行是图顶点的数量，一个正整数 $N$ 。
接下来 $N$ 行，每行 $N$ 个字符。第 $i$ 行第 $j$ 列的 1 表示顶点 $i$ 到 $j$ 有边，0 则表示无边。

输出格式

输出一行一个整数，表示该图的连通数。

样例 #1

样例输入 #1

样例输出 #1

提示

对于 $100 \%$ 的数据， $1 \le N \le 2000$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
bitset<2000>d[2000];
char s[2020];
int n, z;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%s", s);
		for (int j = 0; j < n; j++) {
			if (s[j] == '1') {
				d[i][j] = 1;
			}
		}
		d[i][i] = 1;
	}
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			if (d[i][k]) {
				d[i] |= d[k];
			}
		}
	}
	for (int i = 0; i < n; i++) {
		z += d[i].count();
	}
	printf("%d\n", z);
}

题解

P4306 [JSOI2010]连通数
if we can from i to j
如果可以从i到j
d[i][j] = 1
否则
d[i][j] = 0

读入n行n列的01矩阵
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        scanf("%1d", &d[i][j]);
    }
    d[i][i] = 1; // 自己到自己一定可以
}

直接传递闭包
for (int k = 0; k < n; k++)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (d[i][k] && d[k][j])
            {
                d[i][j] = 1;
            }
        }
    }
}

可以调整 if 的顺序
for (int k = 0; k < n; k++)
{
    for (int i = 0; i < n; i++)
    {
        if (d[i][k] == 1)
        {
            for (int j = 0; j < n; j++)
            {
                d[i][j] |= d[k][j];
            }
        }
    }
}

bitset<2000> d[2000];
for (int k = 0; k < n; k++)
{
    for (int i = 0; i < n; i++)
    {
        if (d[i][k] == 1)
        {
            d[i] |= d[k];
        }
    }
}

最后数一下 d 里面有多少个 1
count how many 1s in d[][]

bitset 有函数 count 数有多少个 1

abc257_d Jumping Takahashi 2

https://atcoder.jp/contests/abc257/tasks/abc257_d
n个点
如果想从点i移动到点j需要满足
Pi * S >= abs(Xi - Xj) + abs(Yi - Yj)
其中S是自己的能力
你来选择起点，目标是能通过若干次跳跃到达每个终点（能跳过去即可，不需要跳回来）
问能力值最小需要多少？

参考代码

Error: ENOENT: no such file or directory, open '/Users/wwwwodddd/Dropbox/Github/Informatics/solutions/abc257_d_s.md'