最新 | U571839 千本桜 题解

思路

本题是一个最小直径生成树(MDST)的模板题。

详细的思路等请参考OI-Wiki上的讲解。

std

/**
 * @file hatsune.cpp
 * @brief Solution of Luogu U571839
 * @date 2025-08-21
 */
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
#define ll long long
using namespace std;

constexpr int MAXN = 510;
ll d[MAXN][MAXN], rk[MAXN][MAXN], val[MAXN];
constexpr ll INF = 1e17;
int n, m;

bool cmp(int a, int b) { return val[a] < val[b]; }

void floyd()
{
    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]);
}

struct node
{
    ll u, v, w;
} a[MAXN * (MAXN - 1) / 2];

int main()
{
    for (int i = 1; i <= 501; ++i)
        for (int j = 1; j <= 501; ++j)
            d[i][j] = INF;
    for (int i = 1; i <= 501; ++i)
        d[i][i] = 0;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i)
    {
        ll u, v, w;
        scanf("%lld %lld %lld", &u, &v, &w);
        w *= 2;
        d[u][v] = w, d[v][u] = w;
        a[i].u = u, a[i].v = v, a[i].w = w;
    }
    floyd();
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            rk[i][j] = j;
            val[j] = d[i][j];
        }
        sort(rk[i] + 1, rk[i] + 1 + n, cmp);
    }
    ll P = 0, ansP = INF;
    for (int i = 1; i <= n; i++)
    {
        if (d[i][rk[i][n]] * 2 < ansP)
        {
            ansP = d[i][rk[i][n]] * 2;
            P = i;
        }
    }
    int f1 = 0, f2 = 0;
    ll disu = INT_MIN, disv = INT_MIN, ansL = INF;
    for (int i = 1; i <= m; i++)
    {
        ll u = a[i].u, v = a[i].v, w = a[i].w;
        for (int p = n, i = n - 1; i >= 1; i--)
        {
            if (d[v][rk[u][i]] > d[v][rk[u][p]])
            {
                if (d[u][rk[u][i]] + d[v][rk[u][p]] + w < ansL)
                {
                    ansL = d[u][rk[u][i]] + d[v][rk[u][p]] + w;
                    f1 = u, f2 = v;
                    disu = (d[u][rk[u][i]] + d[v][rk[u][p]] + w) / 2 - d[u][rk[u][i]];
                    disv = w - disu;
                }
                p = i;
            }
        }
    }
    printf("%lld\n", min(ansP, ansL) / 2);
    return 0;
}