形式化题目

给定一张无向图 $G=(V,E)$：金属环是顶点，$|V| = n$，编号 $1, 2, \dots, n$；绳索是边，每条边长度相同。同一条绳索的两个端点不同，允许重边。

选两个不同的顶点 $L, R$ 分别向两边拉到最远。当 $L$ 到 $R$ 存在多个绳索数相等的连接方法时，只有其中一条被算作拉紧，不得合并统计。

记 $\operatorname{dist}(u,v)$ 为从 $u$ 到 $v$ 最少要经过的绳索数（$u, v$ 不连通时不存在）。求

即把每条绳索看成单位长度时图的直径；没有任何连通点对时答案为 $0$。

正解

思路

先弄清"拉紧"到底数的是哪些绳索。

每条绳索长度都相同，设长度为 $\ell$。把 $L$ 和 $R$ 往两边拉，能拉开的距离不可能超过 $\operatorname{dist}(L,R) \cdot \ell$——因为 $L$ 与 $R$ 之间至少要跨过 $\operatorname{dist}(L,R)$ 条绳索。当拉开到这个距离时，$L$ 与 $R$ 之间的那条最短路径上的绳索全部被拉成直线，恰好 $\operatorname{dist}(L,R)$ 条绳索被拉紧。

也就是说，一对环的得分就是它们之间的最少绳索数，而不是任何几何摆放里可能绷直的绳索总数。题面注释把这条口径写得很死：“如果像样例那样 1-2-4-3-5-6-1 构成了一个环，我们认为拉 1 和 3 时只能拉紧一边（1-2-4-3 或 3-5-6-1）而不算全部拉紧”，以及"当两个环之间有几个绳索数相等的连接方法时，只算其中一条连接方法拉紧"。换句话说，"只算一条"是题面的规定：即使多条等长路径在某个摆放里都能绷直，也只取其中一条的长度计数。

样例的六元环正好说明这个差别。环上的边是 $1\!-\!2\!-\!4\!-\!3\!-\!5\!-\!6\!-\!1$，取 $L=1$、$R=3$：

flowchart LR
  n1((1)) --- n2((2)) --- n4((4)) --- n3((3)) --- n5((5)) --- n6((6)) --- n1

从 1 到 3 有两条步数相同的走法：$1 \to 2 \to 4 \to 3$ 和 $1 \to 6 \to 5 \to 3$，都经过 3 条绳索。如果把它们并起来数，这个六元环的 6 条绳索全都会被算上；但题面规定只算一条，所以 $L=1, R=3$ 的得分是 $3$，与样例输出一致。这也解释了 $d(1,3) = 3$ 是取较短弧长的结果：环上一对点有两条弧，最少绳索数就是较短的那条。

于是问题变成求图的直径。

因为绳索等长（边权全为 1），"最少绳索数"就是无权图里的最短路长度。答案就是所有连通点对的最短路最大值。$L$ 与 $R$ 不连通时一条绳索也拉不紧，贡献 $0$，不参与取最大。

为什么用 Floyd。

要求的是任意两点之间的距离，$n \leqslant 100$，$O(n^3)$ 的 Floyd 一次就能得到完整的距离矩阵：

第 $k$ 轮结束时，dist[i][j] 表示"只允许把编号 $< k$ 的顶点当中转点"时 $i \to j$ 的最少边数；$k$ 走完 $0 \dots n-1$ 就放开了所有中转点。$100^3 = 10^6$ 次松弛在毫秒级完成。

距离矩阵与答案（样例，行列都是环编号）：

观察两点：矩阵关于主对角线对称（因为绳索是无向的，$d(u,v) = d(v,u)$，所以最后只需枚举 $u < v$）；最大值 $3$ 出现在 $(1,3)$、$(2,5)$、$(4,6)$ 三对上，正是环上相隔半圈的点对，也就是答案。

最后的细节。 输出前只对连通点对取最大：

1max((dist[u][v] for u, v in combinations(range(n), 2) if dist[u][v] < INF), default=0)

combinations(range(n), 2) 直接给出所有 $u < v$ 的下标对，if dist[u][v] < INF 跳过不连通点对，default=0 兜住"整张图一条绳索都没有"的情形。

实现上把两件事分开：all_pairs_shortest_paths 只回答"任意两个环之间最少要经过几条绳索"，solve 负责读入、调用、取最大并输出。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int INF = 1000000000;

int n, m;
int dist[105][105];   // 两环之间最少经过的绳索数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dist[i][j] = (i == j ? 0 : INF);

    // 成对读边，奇数落单的 token 自动丢弃（与原版一致）
    int a, b;
    while (cin >> a >> b) {
        dist[a - 1][b - 1] = dist[b - 1][a - 1] = 1;
    }

    // Floyd
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            if (dist[i][k] < INF) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    int ans = 0;
    for (int u = 0; u < n; u++)
        for (int v = u + 1; v < n; v++)
            if (dist[u][v] < INF && dist[u][v] > ans)
                ans = dist[u][v];
    cout << ans << "\n";
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 02:10
# update_at: 2026-10-02 02:10

import sys
from itertools import combinations

INF = 10**9  # 不连通哨兵；n <= 100，真实最短路长度最多 99


def all_pairs_shortest_paths(n: int, edges: list[tuple[int, int]]) -> list[list[int]]:
    """回答"任意两个环之间最少要经过几条绳索"：dist[u][v] 即两环距离，INF 表示不连通。"""
    # 环用 0 基编号；对角线为 0，其余先当作不连通
    dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    for u, v in edges:
        dist[u][v] = dist[v][u] = 1  # 同一对环之间的重边只留一条，多出的绳永远拉不紧

    # Floyd：第 k 轮允许中转环 k，把整行松弛为"原值"与"先到 k 再走 k->j"的逐列较小者
    for k in range(n):
        row_k = dist[k]
        for i, row_i in enumerate(dist):
            reach = row_i[k]  # i 到中转环 k 的距离
            if reach < INF:
                dist[i] = [min(have, reach + via) for have, via in zip(row_i, row_k)]
    return dist


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    m = next(data)  # 题面声明的绳索数（真实数据可能虚高，按实际 token 成对取边）
    # zip 每轮消费两个 token，奇数落单自动丢弃：与原版按实际数据成对取边一致
    edges = [(a - 1, b - 1) for a, b in zip(data, data)]  # 题面编号 1..n

    dist = all_pairs_shortest_paths(n, edges)

    # 拉紧 L 和 R 时，只有那条最短路径上的绳索会绷直，所以一条路径的长度就是能拉紧的绳索数；
    # 枚举所有环对取最大，不连通的环对一条也拉不紧。
    print(
        max(
            (dist[u][v] for u, v in combinations(range(n), 2) if dist[u][v] < INF),
            default=0,
        )
    )


if __name__ == "__main__":
    solve()

复杂度

• 时间：建图 $O(n^2 + m)$，Floyd $O(n^3)$，取最大 $O(n^2)$，总计 $O(n^3)$。$n = 100$ 时约 $10^6$ 次松弛，实测单点约 $0.02$ s。
• 空间：距离矩阵 $O(n^2)$，绳索列表 $O(m) = O(n^2)$，总计 $O(n^2)$。

总结

本题没有几何计算，全部难度集中在把题意翻译成图论语言：

1. 绳索等长 ⇒ 两个环能拉开的距离正比于"最少要经过几条绳索"，被拉紧的绳索恰好构成一条最短路径，得分 = $\operatorname{dist}(L, R)$；
2. 题面规定等长的多条连接方法只算一条，所以答案不是这些路径的并集大小（样例的六元环若取并集会得到 6 而不是 3）；
3. 于是答案就是所有连通点对最短路的最大值，即单位边权图的直径，$O(n^3)$ 的 Floyd 一次算完所有点对。

要点提醒：重边只需在邻接矩阵里写一次 1（多余的绳索永远拉不紧）；不连通的点对不能参与取最大；$n \leqslant 100$ 使 $O(n^3)$ 富余，若 $n$ 放大到 $10^4$ 就该改用 $n$ 次 BFS，而不是继续用 Floyd。同样的算法在 C++ 里就是 dist[a][b] = dist[b][a] = 1; 加三重 for 松弛，Python 版的差别只是把最内层循环写成 zip 加列表推导。