最小直径生成树模板

求最小直径生成树。

称一棵树的直径的中点（可能在边上）为图的绝对中心。那么 MDST 实际上是以绝对中心为起点的最短路生成树。考虑如何求 MDST 。如果是刚好在点上，那么是这个点到两个距离最大的两个点的距离和（两个距离相等）。如果是在边上，考虑枚举边 $(u, v, w)$ ，距离 $u$ 点 $x$ 处，如果直径的一半为 $k$ ，那么对于每个点 $i$ 都有 $ \min(d _ {i, u} + x, d _ {i, v} + w - x) \le k$ ，即一个折线函数。那么 $k$ 实际上为这些的最大值。如图

观察函数上的谷点，可以发现，将到 $u$ 点排序，那么每个点一定是与上一个点的函数交点，满足 $d _ {u, p _ 1} > d _ {u, p _ 2}, d _ {v, p _ 1} < d _ {v, p _ 2}$ ，那么维护上一个点，可以 $O(n)$ 找到这个点。

查看代码

#include <cstdio>
#include <queue>
#include <algorithm>
#define fi first
#define se second
#define mp make_pair
using namespace std;
template <class Type>
void read (Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type, class ...rest>
void read (Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write (Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar('0' + x % 10);
}
typedef pair <int, int> PII;
const int N = 1e3 + 10, M = 2e3 + 10, inf = 1e9;
int n, m, d[N][N], p[N][N];
int idx, hd[N], nxt[M], edg[M], wt[M];
struct Edge { int u, v, w; } e[N];
void add (int a, int b, int c)
{
    nxt[++idx] = hd[a];
    hd[a] = idx;
    edg[idx] = b;
    wt[idx] = c;
}
void dijkstra (int st, int *f)
{
    for (int i = 1; i <= n; ++i) f[i] = inf;
    f[st] = 0;
    priority_queue < PII, vector <PII> , greater <PII> > q;
    q.push(mp(f[st], st));
    while (!q.empty())
    {
        int t = q.top().se; q.pop();
        for (int i = hd[t]; i; i = nxt[i])
            if (f[t] + wt[i] < f[edg[i]])
            {
                f[edg[i]] = f[t] + wt[i];
                q.push(mp(f[edg[i]], edg[i]));
            }
    }
}
int main ()
{
    read(n, m);
    for (int i = 1; i <= m; ++i)
    {
        read(e[i].u, e[i].v, e[i].w);
        add(e[i].v, e[i].u, e[i].w);
        add(e[i].u, e[i].v, e[i].w);
    }
    for (int i = 1; i <= n; ++i)
    {
        dijkstra(i, d[i]);
        for (int j = 1; j <= n; ++j) p[i][j] = j;
        sort(p[i] + 1, p[i] + n + 1, [&](int a, int b) { return d[i][a] < d[i][b]; });
    }
    int res = inf;
    for (int i = 1; i <= n; ++i)
        res = min(res, d[i][p[i][n - 1]] + d[i][p[i][n]]);
    for (int i = 1; i <= m; ++i)
        for (int j = n - 1, k = n; j; --j)
            if (d[e[i].v][p[e[i].u][j]] > d[e[i].v][p[e[i].u][k]])
                res = min(res, d[e[i].u][p[e[i].u][j]] + d[e[i].v][p[e[i].u][k]] + e[i].w), k = j;
    write(res);
    return 0;
}