1 条题解

  • 0
    @ 2026-11-15 14:01:48

    题目分析

    • 考点:图论,bfs,贪心。
    • 难度:CSP-J T4

    测试点 1~3

    给暴力留的分。

    测试点4~8

    先通过bfs求出每个点到另一个点的最短路径的长度 di,jd_{i,j} ,然后暴力枚举四个点 a,b,c,da,b,c,d ,然后求 max⁡(da,b+db,c+dc,d)\max(d_{a,b}+d_{b,c}+d_{c,d}) 就可以了。

    复杂度 O(n4)O(n^4) 。

    测试点9~10

    答案就是 33,因为在完全图中,任意两点的最短路都是 11 。

    测试点11~15

    同样求出 di,jd_{i,j} ,然后暴力枚举三个点 a,b,ca,b,c ,然后求出离 cc 点最远的点 fcf_c,但是 fcf_c 可能是 aa 或者 bb ,所以需要求出离 cc 点第二远的点 gcg_c,第三远的点 hch_c ,这样就一定可以找出那个最远的点。

    复杂度是 O(n3)O(n^3) 。

    当然也有许多其他做法。

    测试点16~20

    优化上一个算法。

    同样求出 di,jd_{i,j} 和 fi,gi,hif_i,g_i,h_i 。

    我们枚举两个点 a,ba,b ,然后经过 a→ba\to b 的最远路径一定是 fa/ga/ha→a→b→fb/gb/hbf_a/g_a/h_a\to a\to b\to f_b/g_b/h_b 其中之一。

    依次考虑这几种情况,排除掉非法的情况(经过相同的点),直接枚举就可以了。

    复杂度是 O(n2)O(n^2) 。

    • 1

    信息

    ID
    83
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者