P1522 [USACO2.4]牛的旅行 Cow Tours（Floyd多源最短路）

洛谷：牛的旅行 Cow son Tours

毒瘤题意（确信）

此题数据很小，但题意不好分析

洛谷题解整理的概念就很好（分析能力%%%）：

1. 牧区： 对应一个点。
2. 牧区之间的距离：实际上是两点之间的 最短路。 不要理解成欧几里得距离。只有 直接连接 的时候，才可以计算欧几里得距离。
3. 牧场： 一个连通块。
4. 牧场直径： 一个牧场的直径是这个牧场所有的牧区（点）之间 距离 的最大值。 说的绕一点就是 所有的任意两点间的最短路的最大值。
5. 使用一条边连接两个牧场，使得合成的一个新的牧场的直径最小。意思是加入一条边之后，使得新的牧场的所有点对之间 最短路 的最大值 最小。

题目中所有的距离，都是最短路的意思，并不是欧几里得距离

而对于任意两个将要合并的连通块：

设将要合并的两个连通块为 A,B，新添加的边为 ( i ，j )（其中 i ∈A，j ∈B），新连通块为 S。

考虑连上 ( i ，j ) 边后，S 连通块直径是怎样构成的可以分为三种情况：

1. A 连通块的直径；
2. B 连通块的直径；
3. A 连通块里从 i 点出发的最远路径 + ( i ，j ) 这一条边 + B 连通块里从 j 点出发的最远路径。

我们只需要用Floyd算法，记录每一个点能到达的所有点的最短路距离的max。相当于预处理，对于连通块的最大直径也是如此。

通过这样的预处理，时间复杂度就只取决于Floyd的O(n^3)了

代码如下：

#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define cout_double(a) cout << setiosflags(ios::fixed) << setprecision(a)
#define sca scanf
#define pri printf
#define ul u << 1
#define ur u << 1 | 1
//#pragma GCC optimize(2)
using namespace std;typedef long long ll;
typedef pair<int, int> PII;const int N = 210, M = 100010;
int INF = 0x3f3f3f3f, mod = 100003;
ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, T, S;
int p[N];
double w[N][N], mxblock[N], mxnode[N];
//mxb存储任意一个连通块的最大直径，mxn存储任意一个点最短路的max
char s[N];
struct node
{double x, y;
}nod[N];int find(int x) {if (p[x] != x)p[x] = find(p[x]);return p[x];
}double check(node a, node b) { //计算距离，这里的距离才是欧几里得距离return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}void floyd() { //标准floydfor (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
}int main() {cin >> n;for (int i = 1; i <= n; i++) {p[i] = i;for (int j = 1; j <= n; j++)//初始化处理好if (i == j)w[i][j] = 0;else w[i][j] = 1e16;}for (int i = 1; i <= n; i++) {double a, b;sca("%lf%lf", &a, &b);nod[i] = { a,b };//记录点}for (int i = 1; i <= n; i++) {sca("%s", s + 1);for (int j = 1; j <= n; j++) {if (s[j] == '1') { //有边就相连w[i][j] = min(w[i][j], check(nod[i], nod[j]));int fi = find(i), fj = find(j);p[fi] = fj;//维护连通块}}}floyd();for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)if (w[i][j] != 1e16)//极值代表不连通，所有最短路取maxmxnode[i] = max(mxnode[i], w[i][j]);for (int i = 1; i <= n; i++) {int fi = find(i);//连通块的直径相当于内部所有点的mxn的maxmxblock[fi] = max(mxblock[fi], mxnode[i]);}double mi = 1e16;//结果求max的minfor (int i = 1; i <= n; i++)for (int j = i + 1; j <= n; j++) { //枚举任意两点能形成的边int fi = find(i), fj = find(j);//不在同一块中才相连if (fi != fj) {mi = min(mi, max({ mxblock[fi],mxblock[fj],mxnode[i] + mxnode[j] + check(nod[i],nod[j]) }));//连通块直径构成的三种情况取max}}pri("%.6f", mi);return 0;
}

Acwing：牛的旅行

#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define sca scanf
#define pri printf
#define ul u << 1
#define ur u << 1 | 1
//#pragma GCC optimize(2)
//[博客地址](https://blog.csdn.net/weixin_51797626?t=1) 
using namespace std;typedef long long ll;
typedef pair<int, pair<int, int>> PII;const int N = 210, M = 10010, MM = 3000010;
int INF = 0x3f3f3f3f, mod = 100003;
ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, T, S, D;
int p[N];
double w[N][N], zh[N], bzh[N];
struct node
{int x, y;
}nod[N];int find(int x) {if (p[x] != x)p[x] = find(p[x]);return p[x];//经典bug —— return x
}double dist(node a, node b) {return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}void floyd() {for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
}int main() {cin >> n;m = 0;for (int i = 1; i <= n; i++) {int x, y;cin >> x >> y;nod[i] = { x,y };p[i] = i;//初始化for (int j = 1; j <= n; j++)if (i != j)w[i][j] = 1e16;}for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) {int t;sca("%1d", &t);if (t) {w[i][j] = min(w[i][j], dist(nod[i], nod[j]));int fi = find(i), fj = find(j);p[fi] = fj;}}floyd();for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)if (w[i][j] != 1e16)zh[i] = max(zh[i], w[i][j]);double mx = -1;for (int i = 1; i <= n; i++) {int fi = find(i);bzh[fi] = max(bzh[fi], zh[i]);mx = max(mx, bzh[fi]);//mx 记录直径最大的牧场的直径}double ans = 1e16;for (int i = 1; i <= n; i++)for (int j = i + 1; j <= n; j++) {int fa = find(i), fb = find(j);if (fa != fb) {double x = max({ bzh[fa], bzh[fb], zh[i] + zh[j] + dist(nod[i],nod[j]) });//bug —— zh[i] + zh[j] 写成 zh[fa] + zh[fb]//这是点的最长的最短路，不是连通块的if (x > mx)ans = min(ans, x);else ans = min(ans, mx);//此题与洛谷同名题略有不同//洛谷求的是 两个牧场连成的 新牧场的最小直径//这里求的是 使直径最大的牧场的直径尽可能小，这个值是多少//分析可得，此处枚举了连接两个不同连通块（牧场）的任意一条边//当这两个牧场都不是 之前记录的直径最大的(max)牧场时，相连只有两种情况：// 1.新牧场直径比 mx 大，显然这个牧场成为 max 牧场，与其取min即可 // 2.新牧场直径比 mx 小，显然 max 牧场没变，与 mx 取min即可//否则，某个牧场和 max 牧场相连，显然新的直径必定 >= mx//这个新牧场肯定是 max 牧场，所以也与 mx 取min即可}}pri("%.6f", ans);return 0;
}