1.先做一边$floyd$,求出每个点到其他各点的最短距离,得到$dist[][]$数组。
2.求出$maxd[]$数组，存放每个点到可达点的距离最大值(遍历dist数组可得)，遍历$maxd$可得到各个牧场内的最大的直径$res1$。
3.连接两个不在同一牧场的点$(i,j)$，求出新牧场经过路径$d[i][j]$的所有可能直径中的最小值$res2=min(d[i][j]+maxd[i]+maxd[j])$
4.最后的答案就是$res1$和$res2$的最大值。

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 155;
const int INF = 0x3f3f3f3f;
char g[N][N];
double maxd[N];
PII q[N];
double d[N][N];
int n;
double get_dist(int i, int j)
{double dx = q[i].x - q[j].x, dy = q[i].y - q[j].y;return sqrt(dx * dx + dy * dy);
}
int main()
{cin >> n;for (int i = 1; i <= n; i ++ )cin >> q[i].x >> q[i].y;for (int i = 1; i <= n; i ++ )cin >> g[i];for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ ){if (i != j){if (g[i][j - 1] == '0') d[i][j] = INF;else d[i][j] = get_dist(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]);double res1 = 0;for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )if (d[i][j] < INF) {maxd[i] = max(maxd[i], d[i][j]);res1 = max(res1, d[i][j]);}double res2 = INF;for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ ){if (d[i][j] >= INF)res2 = min(res2, get_dist(i, j) + maxd[i] + maxd[j]);}printf("%.6lf", max(res1, res2));return 0;
}

给定若干个元素和若干对二元关系且关系具有传递性“通过传递性推导出尽量多的元素之间的
关系”的问题便被称为传递闭包。
本题的主要思想就是考虑枚举到每一组关系时，我们能不能推出所有点对之间的关系，或者说会不会出现矛盾的情况。
我们定义$d[i][j]$表示$i,j$两个点之间时候存在小于关系，使用floyd推出点对之间的关系，$d[i][j]|=d[i][k]\&d[k][j]$。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 26;
int g[N][N];
int d[N][N];
bool st[N];
int n, m;
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];}
int check()
{for (int i = 0; i < n; i ++ )if (d[i][i]) return 2;for (int i = 0; i < n; i ++ )for (int j = 0; j < i; j ++ )if (!d[i][j] && !d[j][i]) return 0;return 1;
}
char get_min()
{for (int i = 0; i < n; i ++ ){if (st[i]) continue;bool flag = true;for (int j = 0; j < n; j ++ ){if (!st[j] && d[j][i]){flag = false;break;}}if (flag){st[i] = true;return i + 'A';}}
}
int main()
{while (cin >> n >> m, n || m){memset(g, 0, sizeof g);int type = 0, t;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;}}if (!type) puts("Sorted sequence cannot be determined.");else if (type == 2) printf("Inconsistency found after %d relations.\n", t);else{memset(st, 0, sizeof st);printf("Sorted sequence determined after %d relations: ", t);for (int i = 0; i < n; i ++ ) printf("%c", get_min());printf(".\n");}}return 0;
}

我们考虑依次求出最大值为k且包含k的环的长度。
对于一个环$i-k-j-...-i$来说，环的长度为$dist[i][j]+w[i][k]+w[k][j]$,其中$dist[i][j]$为i到j的最短路，$w[i][k]+w[k][j]$为两条边权之和。我们对floyd算法进行分析：

 for (int k = 1; k <= n; k ++){//每次我们循环到这个位置时，已经求得了经过点不大于//k-1的两点间的最短路径，正好对应了上面的dist[i][j],//也正因此我们可以在此处来求最大值为k且包含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]);}

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 110, M = 10010;
int g[N][N];
int d[N][N];
int pos[N][N];
int path[N];
int n, m;
int cnt;
void get_path(int i, int j)
{int u = pos[i][j];if (u == 0) return ;get_path(i, u);path[cnt ++ ] = u;get_path(u, j);return ;
}
int main()
{cin >> n >> m;memset(g, 0x3f, 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);}memcpy(d, g, sizeof d);int res = 0x3f3f3f3f;                                                                                                                                                       for (int k = 1; k <= n; k ++ ){for (int i = 1; i < k; i ++ ){for (int j = i + 1; j < k; j ++ ){if (res > (ll)d[i][j] + g[i][k] + g[k][j]){res = d[i][j] + g[i][k] + g[k][j];cnt = 1;get_path(i, j);path[cnt ++ ] = j, path[cnt ++ ] = k, path[cnt ++ ] = i;}}}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 == 0x3f3f3f3f) cout << "No solution." << endl;else{for (int i = 1; i < cnt; i ++ )cout << path[i] << " ";}return 0;
}

$d[a+b][i][j]$表示经过边数为$a+b$时从$i$到$j$的最短路径。
d [ a + b ] [ i ] [ j ] = m i n { d [ a ] [ i ] [ k ] + d [ b ] [ k ] [ j ] } d[a+b][i][j]=min\{d[a][i][k]+d[b][k][j]\} d[a+b][i][j]=min{d[a][i][k]+d[b][k][j]}

如果一个一个枚举的话，需要$O(n^4)$,要一个一个往上加边数，从1到2到3…到k再枚举$i,j,k$,时间复杂度太大过不了
往上加的时候，发现可以利用快速幂(二进制)的思想来处理最外层的循环往上加边数的限制，从而将时间复杂度降成$(n^{3}logn)$
把$g$数组，也就是一开往里读入的图，通过不断地倍增，在需要的时候，也就是$k\&1=1$时,把$res$与$g$数组，进行folyd相加
例如，通过倍增，把$g[i][j]$更新成了恰好经过a条边的最短路，而此时$res[i][j]$数组更新成了恰好经$b$条边的最短路,这样把两者放在一块开始更新，$res[i][j]$就会更新成了从i到j恰好经过$a+b$条边的最短路
在更新前会开个$temp$临时数组来存暂时要求的$res$数组，因为是把两个数组旧的$res$和$g$相加，来更新新$res$数组
不能用更新出来的$res$值，来再更新自己，那样就违背了边数限制，所以先用$temp$数组来临时存答案，求完了再把值赋给$res$，从而更新它。

#include <iostream>
#include <cstring>
#include <map>
using namespace std;const int N = 210, M = 110;
int d[N][N];
int res[N][N];
int k, n, m, s, e;
void mul(int a[][N], int b[][N], int c[][N])
{static int temp[N][N];memset(temp, 0x3f, sizeof temp);for (int k = 1; k <= n; k ++ )for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ ){temp[i][j] = min(temp[i][j], b[i][k] + c[k][j]);}memcpy(a, temp, sizeof temp);
}
void qmi()
{memset(res, 0x3f,sizeof res);for (int i = 1; i <= n; i ++ ) res[i][i] = 0;while (k){if (k & 1) mul(res, res, d);mul(d, d, d);k >>= 1;}
}
int main()
{cin >> k >> m >> s >> e;map<int, int>ids; memset(d, 0x3f, sizeof d);if (!ids.count(s)) ids[s] = ++ n;if (!ids.count(e)) ids[e] = ++ n;for (int i = 1; i <= m; i ++ ){int a, b, c;cin >> c >> a >> b;if (!ids.count(a)) ids[a] = ++ n;if (!ids.count(b)) ids[b] = ++ n;a = ids[a], b= ids[b];d[a][b] = d[b][a] = min(d[a][b], c);}qmi();cout << res[ids[s]][ids[e]];return 0;
}