【图论】Floyd

算法提高课笔记）

例题

牛的旅行

原题链接

农民John的农场里有很多牧区，有的路径连接一些特定的牧区。

一片所有连通的牧区称为一个牧场。

但是就目前而言，你能看到至少有两个牧区不连通。

现在，John想在农场里添加一条路径（注意，恰好一条）。

一个牧场的直径就是牧场中最远的两个牧区的距离（本题中所提到的所有距离指的都是最短的距离）。

考虑如下的两个牧场，每一个牧区都有自己的坐标：

图 1 是有 5 个牧区的牧场，牧区用“*”表示，路径用直线表示。

图 1 所示的牧场的直径大约是 12.07106, 最远的两个牧区是 A 和 E，它们之间的最短路径是 A-B-E。

图 2 是另一个牧场。

这两个牧场都在John的农场上。

John将会在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。

注意，如果两条路径中途相交，我们不认为它们是连通的。

只有两条路径在同一个牧区相交，我们才认为它们是连通的。

现在请你编程找出一条连接两个不同牧场的路径，使得连上这条路径后，所有牧场（生成的新牧场和原有牧场）中直径最大的牧场的直径尽可能小。

输出这个直径最小可能值。

输入格式

第 1 行：一个整数 N, 表示牧区数；

第 2 到 N+1 行：每行两个整数 X,Y， 表示 N 个牧区的坐标。每个牧区的坐标都是不一样的。

第 N+2 行到第 2*N+1 行：每行包括 N 个数字 ( 0或1 ) 表示一个对称邻接矩阵。

例如，题目描述中的两个牧场的矩阵描述如下：

  A B C D E F G H 
A 0 1 0 0 0 0 0 0 
B 1 0 1 1 1 0 0 0 
C 0 1 0 0 1 0 0 0 
D 0 1 0 0 1 0 0 0 
E 0 1 1 1 0 0 0 0 
F 0 0 0 0 0 0 1 0 
G 0 0 0 0 0 1 0 1 
H 0 0 0 0 0 0 1 0

输入数据中至少包括两个不连通的牧区。

输出格式

只有一行，包括一个实数，表示所求答案。

数字保留六位小数。

数据范围

$1\le N\le 150,$
$0\le X,Y\le 105$

输入样例

8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010

输出样例

22.071068

题意

给出一张图，连通的部分算作一个区域，每个区域的直径为区域中相隔最远的两个点的距离，问在不同区域中添加一条边，得到的最小直径是多少

思路

先建图，然后跑一遍floyd算出和每一个点相隔最远的点的距离

得到的最新直径一定大于等于原来的最大直径，因此可以先求出原来的最大直径maxd[i]

加上一条边[i, j]得到的新直径是maxd[i] + maxd[j] + dist[i][j]

二者取最大值即可

代码

#include <bits/stdc++.h>using namespace std;typedef pair<double, double> PDD;const int N = 155;
const double INF = 1e20;int n;
double d[N][N];
double maxd[N];
char g[N][N];
PDD q[N];double get_dist(PDD a, PDD b)
{double dx = a.first - b.first;double dy = a.second - b.second;return sqrt(dx * dx + dy * dy);
}int main()
{cin >> n;for (int i = 0; i < n; i ++ ) cin >> q[i].first >> q[i].second;for (int i = 0; i < n; i ++ ) cin >> g[i];for (int i = 0; i < n; i ++ )for (int j = 0; j < n; j ++ )if (i == j) d[i][j] = 0;else if (g[i][j] == '1') d[i][j] = get_dist(q[i], q[j]); // ij之间有边else d[i][j] = INF; // ij之间无边// floyd更新最短路for (int k = 0; k < n; 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]);double r1 = 0; // 两个牧场中最长的直径for (int i = 0; i < n; i ++ ){for (int j = 0; j < n; j ++ )if (d[i][j] < INF / 2) // 说明ij之间有边maxd[i] = max(maxd[i], d[i][j]); // 更新与i最远的点距离r1 = max(r1, maxd[i]); // 更新直径}double r2 = INF; // 加边之后的最长值for (int i = 0; i < n; i ++ )for (int j = 0; j < n; j ++ )if (d[i][j] > INF / 2) // 说明ij之间无边 可以加边r2 = min(r2, maxd[i] + maxd[j] + get_dist(q[i], q[j]));printf("%.6lf\n", max(r1, r2));
}

排序

原题链接

给定 n 个变量和 m 个不等式。其中 n 小于等于 26，变量分别用前 n 的大写英文字母表示。

不等式之间具有传递性，即若 A>B 且 B>C，则 A>C。

请从前往后遍历每对关系，每次遍历时判断：

如果能够确定全部关系且无矛盾，则结束循环，输出确定的次序；
如果发生矛盾，则结束循环，输出有矛盾；
如果循环结束时没有发生上述两种情况，则输出无定解。

输入格式

输入包含多组测试数据。

每组测试数据，第一行包含两个整数 n 和 m。

接下来 m 行，每行包含一个不等式，不等式全部为小于关系。

当输入一行 0 0 时，表示输入终止。

输出格式

每组数据输出一个占一行的结果。

结果可能为下列三种之一：

• 如果可以确定两两之间的关系，则输出 Sorted sequence determined after t relations: yyy...y.,其中t指迭代次数，yyy...y是指升序排列的所有变量。
• 如果有矛盾，则输出： Inconsistency found after t relations.，其中t指迭代次数。
• 如果没有矛盾，且不能确定两两之间的关系，则输出 Sorted sequence cannot be determined.。

数据范围

$2\le n\le 26，变量只可能为大写字母A\sim Z。$

输入样例1

4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0

输出样例1

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

输入样例2

6 6
A<F
B<D
C<E
F<D
D<E
E<F
0 0

输出样例2

Inconsistency found after 6 relations.

输入样例3

5 5
A<B
B<C
C<D
D<E
E<A
0 0

输出样例3

Sorted sequence determined after 4 relations: ABCDE.

题意

从前到后遍历给出的关系，如果能确定所有关系就直接输出当前次数和关系，如果前后矛盾则输出矛盾，如果得不到最终关系就输出得不到最终关系

思路

传递闭包

已知a>b b>c 一定可以推出 a>c，根据这个性质，我们可以在得到每个新的判断时进行传递，看看是否不满足原先已知的结论，如果不满足就会出现i和i的关系确定的结果

代码

#include <bits/stdc++.h>using namespace std;const int N = 26;int n, m;
bool g[N][N], d[N][N]; // 表示两个字母之间关系（前一个字母小于后一个字母）是否确定
bool st[N];void floyd()
{memcpy(d, g, sizeof d);for (int k = 0; k < n; k ++ )for (int i = 0; i < n; i ++ )for (int j = 0; j < n; j ++ )d[i][j] |= d[i][k] && d[k][j]; // 如果有i->k k->j的边 那就加上i->j的边
}int check()
{for (int i = 0; i < n; i ++ )if (d[i][i]) return 2; // 出现矛盾返回2for (int i = 0; i < n; i ++ )for (int j = 0; j < i; j ++ )if (!d[i][j] && !d[j][i])return 0; // 遍历所有数对 没确定返回0return 1; // 确定就返回1
}char get_min()
{for (int i = 0; i < n; i ++ )if (!st[i]){bool flag = true;for (int j = 0; j < n; j ++ )if (!st[j] && d[j][i]) // 如果有没出现过的j比i还小的话说明i不是最小值{flag = false;break;}if (flag) // 否则i就是当前没出现过的数中的最小值{st[i] = true;return 'A' + i;}}
}int main()
{while (cin >> n >> m, n || m){memset(g, 0, sizeof g);int type = 0, t; // type表示目前关系未确定/确定/矛盾for (int i = 1; i <= m; i ++ ){char str[5];cin >> str;int a = str[0] - 'A', b = str[2] - 'A';if (!type){g[a][b] = 1;floyd();type = check();if (type) t = i; // t记录经过几次才确定所有关系}}if (!type) puts("Sorted sequence cannot be determined."); // 关系不确定else if (type == 2) cout << "Inconsistency found after " << t << " relations.\n"; // 矛盾else // 确定{memset(st, 0, sizeof st);cout << "Sorted sequence determined after " << t << " relations: ";for (int i = 0; i < n; i ++ ) cout << get_min();cout << ".\n";}}
}

观光之旅

原题链接

给定一张无向图，求图中一个至少包含 3 个点的环，环上的节点不重复，并且环上的边的长度之和最小。

该问题称为无向图的最小环问题。

你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。

输入格式

第一行包含两个整数 N 和 M，表示无向图有 N 个点，M 条边。

接下来 M 行，每行包含三个整数 u，v，l，表示点 u 和点 v 之间有一条边，边长为 l。

输出格式

输出占一行，包含最小环的所有节点（按顺序输出），如果不存在则输出 No solution.。

数据范围

$1\le N\le 100,$
$1\le M\le 10000,$
$1\le l<500$

输入样例

5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

输出样例

1 3 5 2

题意

无向图的最小环裸题

思路

假设环的形式是这样的：（ij均小于k）

那么环的长度就是d[i][j] + g[j][k] + g[k][i]（d代表ij在图上的最短距离，g表示两点之间有边的话 边的长度）

用pos[i][j] = k记录i和j的最短路由k的状态转移，k是路径中编号最大的点

在floyd中循环每个k，如果d[i][j] + g[j][k] + g[k][i]比当前的最小环长度更小就更新一下

使用类似中序遍历的算法求出环中的字母

代码

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 110, INF = 0x3f3f3f3f;int n, m;
int d[N][N], g[N][N];
int pos[N][N];
int path[N], cnt;void get_path(int i, int j)
{if (pos[i][j] == 0) return;// 类似于中序遍历int k = pos[i][j];get_path(i, k);path[cnt ++ ] = k;get_path(k, j);
}int main()
{cin >> n >> m;memset(g, 0x3f3f3f3f, sizeof g);for (int i = 1; i <= n; i ++ ) g[i][i] = 0; // 避免统计自环while (m -- ){int a, b, c;cin >> a >> b >> c;g[a][b] = g[b][a] = min(g[a][b], c);}int res = INF;memcpy(d, g, sizeof d);for (int k = 1; k <= n; k ++ ){for (int i = 1; i < k; i ++ )for (int j = i + 1; j < k; j ++ )if ((ll)d[i][j] + g[j][k] + g[k][i] < res) // 一旦发现比原来的最短路还要短的路径就更新{res = d[i][j] + g[j][k] + g[k][i]; // 最短路长度// 更新最短路中的点cnt = 0;path[cnt ++ ] = k;path[cnt ++ ] = i;get_path(i, j);path[cnt ++ ] = j;}// 更新两点之间的距离 在更新完最小环之后更新所以不会对最小环有影响for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )if (d[i][j] > d[i][k] + d[k][j]){d[i][j] = d[i][k] + d[k][j];pos[i][j] = k;}}if (res == INF) puts("No solution.");else{for (int i = 0; i < cnt; i ++ ) cout << path[i] << ' ';cout << '\n';}
}