图片来源与 $oi-wiki$

引入

这个是一个比较偏门的算法，但是并不排除考察的可能性。其中的思路比较灵活，这里介绍一下，希望起到抛砖引玉的效果。

图的绝对中心

概念，图的绝对中心可以存在于一条边上或某个结点上，该中心到所有点的最短距离的最大值最小。
那么我们首先的关键点就是求出图的绝对中心，我们可以分类讨论，因为我们可以知道图的绝对中心一定到至少两个最远点的距离相同。
那么 $Ans = 2\times \max(dis_{u,i})$ 当绝对中心在点上时。

当绝对中心在边上时，我们可以通过移动绝对中心的位置 $pos$ 可以按照 $\max(dis_{u,i}+x,dis_{v,i}+e_w-x)$ 做出如下图像。那么我们可以枚举每个交点。那么我们可以发现，由于斜率相同。所以我们可以先按 $dis_{u,i}$ 排序，找到第一个 $dis_{v,j} > dis_{v,i}$ 而且 $j < i$ 。那么它们的折线一定构成了一个交点，这时再重新更新 $i$ 。因为我们是从大到小枚举的 $i$ 。而斜率相同，所以不更新 $i$ ，那么下次构成的交点并没有在上图黑线上。

例题

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f=1;ch=getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch=getchar();}
    return f?-x:x;
}
const int N = 210;
struct Edge{int u,v,w;}e[N * N];
int f[N][N],rk[N][N],val[N],n,m;
bool cmp(int a,int b) {return val[a] < val[b];}
int main() {
    n = read();m = read();memset(f,0x3f,sizeof(f));
    for(int i = 1;i <= m;i++) {
        e[i].u = read();e[i].v = read();e[i].w = read();
        f[e[i].u][e[i].v] = f[e[i].v][e[i].u] = e[i].w;
    }
    for(int i = 1;i <= n;i++) f[i][i] = 0;
    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]);
            }
        }
    }
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++) {
            rk[i][j] = j;val[j] = f[i][j];
        }
        sort(rk[i] + 1,rk[i] + 1 + n,cmp);
    }
    int ans = 0x3f3f3f3f;
    for(int i = 1;i <= n;i++) ans = min(ans,f[i][rk[i][n]] * 2);
    for(int i = 1;i <= m;i++) {
        int p = n;
        for(int j = n - 1;j >= 1;j--) {
            if(f[e[i].v][rk[e[i].u][j]] > f[e[i].v][rk[e[i].u][p]]) {
                ans = min(ans,f[e[i].u][rk[e[i].u][j]] + f[e[i].v][rk[e[i].u][p]] + e[i].w);
                p = j; 
            }
        }
    }
    printf("%.9f\n",(double)ans/2.0);
    return 0;
}

最小直径生成树

既然我们找到了绝对中心，那么我们只需要从绝对中心做一次单源最短路，就可以找到最小直径生成树。

例题

SPOJ MDST

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f=1;ch=getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch=getchar();}
    return f?-x:x;
}
const int N = 1010,inf = 0x3f3f3f3f;
int f[N][N],rk[N][N],val[N],n;
vector<int> G[N];
struct Edge{int u,v;}e[N * N];
bool cmp(int a,int b) {return val[a] < val[b];}
void bfs(int s) {
    f[s][s] = 0;queue<int> q;
    q.push(s);while(!q.empty()) {
        int x = q.front();q.pop();
        for(auto y:G[x]) {
            if(f[s][y] == inf) f[s][y] = f[s][x] + 1,q.push(y);
        }
    }
}
int main() {
    int T = read();
    while(T--) {
        int ecnt = 0;
        n = read();memset(f,0x3f,sizeof(f));
        for(int i = 1;i <= n;i++) G[i].clear();
        for(int i = 1;i <= n;i++) {
            int id = read(),m = read();
            while(m--) {
                int a = read();G[id].push_back(a);
                e[++ecnt] = (Edge){id,a};
            }
        }
        for(int i = 1;i <= n;i++) {
            bfs(i);
            for(int j = 1;j <= n;j++) rk[i][j] = j,val[j] = f[i][j];
            sort(rk[i] + 1,rk[i] + 1 + n,cmp);
        }
        int ans = 0x3f3f3f3f;
        for(int i = 1;i <= n;i++) ans = min(f[i][rk[i][n]] * 2, ans);
        for(int j = 1;j <= ecnt;j++) {
            int u = e[j].u, v = e[j].v;
            for(int p = n,i = n-1;i >= 1;i--) {
                if(f[v][rk[u][p]] < f[v][rk[u][i]]) {
                    ans = min(ans,f[u][rk[u][i]] + f[v][rk[u][p]] + 1);
                    p = i;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}