usaco-4.1.3 篱笆回路

GitHub跳转原题关系图返回列表

端点用它上面相接的篱笆标号集合编号，篱笆是有权边，区域就是环；枚举每条边禁掉后跑 Dijkstra 求两端最短路，w+dist 取最小。

OJ: roj

题目 ID: 2063

难度:提高

标签:图论最短路Dijkstra堆python

创建: 2026-10-01 05:57

更新: 2026-10-07 13:50

前置题目

luogu P4779【模板】单源最短路径（标准版）B 把 A 教的堆优化 Dijkstra 原样当作子程序（detour 里同样是弹出最小距离状态、沿边松弛、以 dictionary 距离表判重），只是额外叠加了把区域周长化为最小环、再逐条禁边求 w+dist 的最小值这一层流程。roj 1382最短路(Spfa)B 的最小环枚举把 A 教的堆优化 Dijkstra 当子程序原样复用：main.py 的 detour 里同样是「松弛成功就压堆、弹出时 if d > dist[x] 跳过过期条目、命中目标点立即返回」，只是加了 banned 禁边参数，A 只跑一次单源最短路，B 把它对每条篱笆各跑一次再取 w+dist 最小值，并另行叠加「相接集合当端点编号」与「区域周长=最小环」两步。

形式化题目

有 $N$ 段篱笆，第 $s$ 段长度为 $L_s$ 。每段篱笆有两个端点；题目不给出任何坐标，只给出"这个端点上还接着哪几段篱笆"：第 $s$ 段的一端与给定的 $N_{1s}$ 段篱笆相接，另一端与给定的 $N_{2s}$ 段篱笆相接（ $1 \leqslant N_{1s}, N_{2s} \leqslant 8$ ，且 $s$ 不会出现在自己的相接列表里）。

篱笆在平面上构成网络，把平面分割成若干区域。求所有区域周长的最小值，即

\min \Bigl\{\, \sum_{f \in F} L_f \;\Bigm|\; F \text{ 是围出某一块封闭区域的篱笆集合} \,\Bigr\}

以样例（ $N = 10$ ）为例，周长最小那块区域由第 2、7、8 段篱笆围成，周长为 $3+5+4=12$ 。

正解

思路

一句话本质：把每段篱笆看成一条带权边、把每个"端点"看成一个顶点，于是"围出一块区域的篱笆"正好是图中的一个环，问题变成求最小环的边权和。

问题一：没有坐标，顶点怎么编号？

题面给不出坐标，但它给了更直接的东西：每个端点上接了哪几段篱笆。反过来读，这就足以确定一个端点是谁——如果篱笆 $f$ 说它这一端接着 $g$ 和 $h$ ，那么这一端的物理身份就是" $f,g,h$ 三段焊在一起的那个点"。

于是把篱笆 $f$ 的某个端点编号定义成集合

\text{key} = \{\, f \,\} \cup \{\, \text{该端相接的篱笆标号} \,\}

同一物理端点无论被哪段篱笆描述，得到的集合都一样；实现里用 tuple(sorted(...)) 当 dict 的键。

样例 fence60 的 10 段篱笆共描述 20 个端点，去重后恰好剩 7 个，与题目 ASCII 图里的 7 个顶点完全吻合：

端点	相接篱笆
A	1, 2, 7
B	1, 6, 10
C	2, 3, 8
D	3, 4
E	4, 5, 9, 10
F	5, 6
G	7, 8, 9

把 10 段篱笆按这个编号接起来，得到下面这张带权无向图（边上的数字是篱笆标号与长度）：

graph LR
    A["A = 1,2,7"] ---|"篱笆 1 / 长 16"| B["B = 1,6,10"]
    A ---|"篱笆 2 / 长 3"| C["C = 2,3,8"]
    C ---|"篱笆 3 / 长 3"| D["D = 3,4"]
    D ---|"篱笆 4 / 长 8"| E["E = 4,5,9,10"]
    E ---|"篱笆 5 / 长 8"| F["F = 5,6"]
    F ---|"篱笆 6 / 长 6"| B
    A ---|"篱笆 7 / 长 5"| G["G = 7,8,9"]
    C ---|"篱笆 8 / 长 4"| G
    G ---|"篱笆 9 / 长 5"| E
    B ---|"篱笆 10 / 长 10"| E

观察重点是：题面那张 ASCII 图里的 7 个顶点在这张图里一一对应，而"围出一块地"在图里的含义就是"顺着边绕一圈回到起点"。图中最短的一圈是 A–C–G，长度 $3+5+4=12$ ，正是样例答案。

问题二：为什么区域和环是同一件事？

两个方向都要成立：

区域 → 环：区域的边界本身就是一条闭回路，沿着它走一圈、把重复经过的顶点去掉，就得到图中的一个环，环长不超过区域周长。所以最小环长 $\leqslant$ 最小区域周长。
环 → 区域：取任意一个环 $C$ 。如果 $C$ 内部没有别的篱笆，那么 $C$ 自己就围出一块地，周长正好是 $|C|$ 。否则在这块地内部继续切：取一条真正把地切成两块的篱笆 $f$ （一端悬空的"刺"切不出两块地，也永远不会成为任何区域的边界，直接跳过），它的两个端点落在这块地边界上，把边界切成两条弧 $a$ 与 $b$ ；而篱笆是直线段，两点之间直线最短，所以 $|f| \leqslant \min(a, b)$ 。设 $a \leqslant b$ ，则切出的两块地中较小者的周长为 $|f| + a \leqslant 2a \leqslant a + b$ ，即不超过切之前那块地的周长。反复切下去，周长始终不增，最后必然得到一块内部再无篱笆的地——它就是一块区域，周长不超过最初的 $|C|$ 。所以最小区域周长 $\leqslant$ 最小环长。

两边取最小值后相等，最小区域周长 $=$ 最小环边权和。注意第二个方向用到了“篱笆都是直线段”这个条件：如果篱笆可以是任意弯曲的曲线，一条绕来绕去的“弦”可以比它切出的两块地的周长都长，两者就不再相等了。

顺带说明多段汇合的情况：一个端点接 3 段以上篱笆（数据里最多接了 8 段）时，几何上它周围被分成多个扇区。但在图模型里，一个环"进入该顶点"和"离开该顶点"可以走任意两条不同的边，不需要知道它们几何上是否相邻——因为小扇区如果被别的篱笆切成更小的区域，那块更小的区域自己也会成为一个环，最终仍会被枚举到。所以把顶点当作"入边出边可自由配对"的普通图顶点，既不会漏掉真实的环，算出的候选值也都对应真实的闭合曲线。

问题三：怎么在 $N \leqslant 100$ 下求最小环？

穷举所有环是不行的—— $N = 100$ 的图里简单环可以有天文数字那么多。标准做法是枚举环上的一条边：

对每条边 $e = (u, v, w)$ ，把 $e$ 从图中删掉，求 $u$ 到 $v$ 的最短路 $d$ ，那么 $w + d$ 就是一个候选答案。

不漏：设最小环是 $C$ 。从 $C$ 里拿走任意一条边 $e$ ，剩下的是一条 $u \to v$ 路径，长 $|C| - w_e$ ；既然它是 $G - e$ 中的一条合法路径，最短路必然 $\leqslant$ 它，于是 $w_e + d \leqslant |C|$ 。候选值不会超过答案。
不假： $G - e$ 中任意一条 $u \to v$ 最短路加上 $e$ 就是一条真实闭合回路，其长度 $\geqslant$ 最小环长。候选值也不会小于答案。

唯一要防的退化情况是"路径一步都不走"：万一某段篱笆的两端编号相同（自环），从 $u$ 到 $u$ 的最短路会返回 $0$ 。实现里让 Dijkstra 先从起点迈出一条边再入堆，保证路径至少含一条边，自环时也能返回真实回路长度。真实数据没有这种输入，但这个处理是免费的。

边只有 $N \leqslant 100$ 条，每条跑一次 Dijkstra 是 $O(N \log N)$ ，总复杂度 $O(N^2 \log N)$ ，绰绰有余。

把样例的枚举过程完整列出来（ $d$ 是禁掉该边后两端点间的最短路）：

篱笆	端点	$w$	$d$	$w+d$
2	A–C	3	9	12
7	A–G	5	7	12
8	C–G	4	8	12
3	C–D	3	17	20
4	D–E	8	12	20
9	G–E	5	15	20
5	E–F	8	16	24
6	F–B	6	18	24
10	B–E	10	14	24
1	A–B	16	20	36

最小值 12 由前三行给出，它们其实是同一个三角形 A–C–G 的三条边——环上每条边被枚举到时都会算出同一个候选值，重复不影响取最小值。

代码

Python 版：

python

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66#!/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-01 05:58
# update_at: 2026-10-01 06:04

import sys
from heapq import heappop, heappush
from collections.abc import Iterator

INF = 10**9  # 篱笆总长不超过 100*255，用它当"走不到"的哨兵

Junction = tuple[int, ...]  # 端点身份 = 在这个端点上相接的篱笆标号集合，同集合即同端点
Fence = tuple[Junction, Junction, int]  # (一端的端点, 另一端的端点, 长度)
Edge = tuple[Junction, int, int]  # (对端端点, 长度, 篱笆标号)


def detour(adj: dict[Junction, list[Edge]], start: Junction, goal: Junction, banned: int) -> int:
    """禁用 banned 号篱笆后，从 start 沿至少一条篱笆走到 goal 的最短长度，走不到返回 INF。

    出发点先迈一步再入堆，所以 start == goal（某段篱笆两端落在同一端点）时
    得到的是一条真正的回路，而不是长度为 0 的空路。
    """
    dist: dict[Junction, int] = {}
    pq: list[tuple[int, Junction]] = []
    for y, w, eid in adj[start]:
        if eid != banned and w < dist.get(y, INF):
            dist[y] = w
            heappush(pq, (w, y))
    while pq:
        d, x = heappop(pq)
        if d > dist[x]:  # 过期堆项
            continue
        if x == goal:
            return d
        for y, w, eid in adj[x]:
            if eid != banned and d + w < dist.get(y, INF):
                dist[y] = d + w
                heappush(pq, (d + w, y))
    return INF


def solve() -> None:
    data: Iterator[int] = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)

    fences: list[Fence] = []
    for _ in range(n):
        s, length, left_count, right_count = next(data), next(data), next(data), next(data)
        left = [next(data) for _ in range(left_count)]
        right = [next(data) for _ in range(right_count)]
        # 题面只给"相接关系"，不给坐标：把"该端点上所有篱笆的标号集合"直接当作端点编号
        fences.append((tuple(sorted(left + [s])), tuple(sorted(right + [s])), length))

    adj: dict[Junction, list[Edge]] = {}
    for eid, (u, v, length) in enumerate(fences):
        adj.setdefault(u, []).append((v, length, eid))
        adj.setdefault(v, []).append((u, length, eid))

    # 每条篱笆轮流充当回路的一环：禁掉它，两个端点之间的最短路就是回路剩下的部分
    print(min(length + detour(adj, u, v, eid) for eid, (u, v, length) in enumerate(fences)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143/**
 * 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-06 10:36
 * update_at: 2026-10-06 10:36
 */
#include <cstdio>
#include <vector>
#include <map>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 105;   // 篱笆段数上限
const int MAXV = 205;   // 端点数量上限：每段篱笆两端，去重后不超过 2*N
const ll INF = (ll)1e18; // “走不到”的哨兵，篱笆总长远小于它

int n;                          // 篱笆段数
int m;                          // 去重后的端点数
int fence_u[MAXN];              // 第 i 段篱笆一端的端点编号
int fence_v[MAXN];              // 第 i 段篱笆另一端的端点编号
ll fence_len[MAXN];             // 第 i 段篱笆的长度
vector<int> adj[MAXV];          // adj[x] 存以 x 为一端的篱笆编号
map<vector<int>, int> vertex_id; // 端点身份（该端点上全部篱笆标号的有序集合）-> 端点编号

ll dist_arr[MAXV];              // Dijkstra 的距离表：dist_arr[x] 为当前起点到 x 的最短长度
bool used[MAXV];                // used[x] 表示 x 的最短路已确定

// 把端点身份映射成编号，没有见过就新建一个。
int get_vertex(const vector<int> &key) {
    map<vector<int>, int>::iterator it = vertex_id.find(key);
    if (it != vertex_id.end()) {
        return it->second;
    }
    vertex_id[key] = m;
    m = m + 1;
    return m - 1;
}

// 禁掉 banned 号篱笆后，从 start 沿至少一条篱笆走到 goal 的最短长度，走不到返回 INF。
// 起点先迈一条边再入堆，所以 start == goal（某段篱笆两端落在同一端点）时得到的是真实回路，而不是空路。
ll dijkstra(int start, int goal, int banned) {
    int i;
    for (i = 0; i < m; i++) {
        dist_arr[i] = INF;
        used[i] = false;
    }

    priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
    for (i = 0; i < (int)adj[start].size(); i++) {
        int e = adj[start][i];
        if (e == banned) {
            continue;
        }
        int y = fence_u[e] + fence_v[e] - start; // 篱笆的另一端
        if (fence_len[e] < dist_arr[y]) {
            dist_arr[y] = fence_len[e];
            pq.push(make_pair(fence_len[e], y));
        }
    }

    while (!pq.empty()) {
        pair<ll, int> top = pq.top();
        pq.pop();
        ll d = top.first;
        int x = top.second;
        if (used[x]) {
            continue;
        }
        used[x] = true;
        if (x == goal) {
            return d;
        }
        for (i = 0; i < (int)adj[x].size(); i++) {
            int e = adj[x][i];
            if (e == banned) {
                continue;
            }
            int y = fence_u[e] + fence_v[e] - x; // 篱笆的另一端
            if (d + fence_len[e] < dist_arr[y]) {
                dist_arr[y] = d + fence_len[e];
                pq.push(make_pair(dist_arr[y], y));
            }
        }
    }
    return INF;
}

int main() {
    int i;
    int j;

    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        int s;
        int length;
        int left_count;
        int right_count;
        scanf("%d %d %d %d", &s, &length, &left_count, &right_count);
        fence_len[i] = length;

        // 题面只给相接关系，不给坐标：把“该端点上全部篱笆的标号集合”当作端点身份。
        vector<int> left_key;
        left_key.push_back(s);
        for (j = 0; j < left_count; j++) {
            int label;
            scanf("%d", &label);
            left_key.push_back(label);
        }
        vector<int> right_key;
        right_key.push_back(s);
        for (j = 0; j < right_count; j++) {
            int label;
            scanf("%d", &label);
            right_key.push_back(label);
        }
        sort(left_key.begin(), left_key.end());
        sort(right_key.begin(), right_key.end());

        fence_u[i] = get_vertex(left_key);
        fence_v[i] = get_vertex(right_key);
        adj[fence_u[i]].push_back(i);
        adj[fence_v[i]].push_back(i);
    }

    // 每条篱笆轮流充当回路的一环：禁掉它，两端点之间的最短路就是回路剩下的部分。
    ll answer = INF;
    for (i = 1; i <= n; i++) {
        ll rest = dijkstra(fence_u[i], fence_v[i], i);
        if (rest < INF) {
            ll candidate = fence_len[i] + rest;
            if (candidate < answer) {
                answer = candidate;
            }
        }
    }
    printf("%lld\n", answer);
    return 0;
}

复杂度

时间复杂度： $O(N^2 \log N)$ 。建图 $O(N \log N)$ ；枚举 $N$ 条边，每条在删边图上跑一次堆优化 Dijkstra， $O(N \log N)$ 。
空间复杂度： $O(N)$ 。邻接表存 $2N$ 条有向边，单次 Dijkstra 的距离表最多 $O(N)$ 项。

总结

本题没有任何坐标，"端点是谁"这个信息就藏在相接列表里：把该端点上全部篱笆的标号集合当作端点的编号，tuple(sorted(...)) 直接就能当哈希键。
建图之后，“围出一块地"就是"图上的一个环”，区域的最小周长就是最小环的边权和。两个方向都要说清：区域边界去掉重复顶点就是环；反过来沿内部篱笆切地时，用"篱笆是直线段、两点间直线最短"可以证明切分不会让最小周长变大。
求最小环不枚举环，而是枚举环上的一条边：删掉它、跑一次两端点的最短路， $w + \operatorname{dist}$ 就是候选值；正确性靠"不漏 + 不假"两端夹逼。
实现上的两个小细节：Dijkstra 从起点先迈一条边，天然绕开自环退化成空路的问题；距离表用 dict + get(y, INF)，省掉给端点分配整数编号的整层代码。

题目描述

农夫布朗的牧场上的篱笆已经失去控制了.它们分成了 1~200 英尺长的线段.只有在线段的端点处才能连接两个线段,有时给定的一个端点上会有两个以上的篱笆.结果篱笆形成了一张网分割了布朗的牧场.布朗想将牧场恢复原样,出于这个考虑,他首先得知道牧场上哪一块区域的周长最小.

布朗将他的每段篱笆从1到N 进行了标号（N=线段的总数）.他知道每段篱笆的有如下属性:

该段篱笆的长度

该段篱笆的一端所连接的另一段篱笆的标号

该段篱笆的另一端所连接的另一段篱笆的标号

幸运的是,没有篱笆连接它自身.

对于一组有关篱笆如何分割牧场的数据,写一个程序来计算出所有分割出的区域中最小的周长.

例如,标号 1~10 的篱笆由下图的形式组成（下面的数字是篱笆的标号）:

text

1
2
3
4
5
6
7
8
9
10
11         1
 +---------------+
 |\             /|
2| \7          / |
 |  \         /  |
 +---+       /   |6
 | 8  \     /10  |
3|     \9  /     |
 |      \ /      |
 +-------+-------+
    4       5

上图中周长最小的区域是由 2,7,8 号篱笆形成的.

INPUT FORMAT

第 1 行: N (1 <= N <= 100)

第 2 行到第 3*N+1 行:

每三行为一组,共 N 组信息:

每组信息的第 1 行有 4 个整数: s, 这段篱笆的标号(1 <= s <= N); Ls, the 这段篱笆的长度 (1 <= Ls <= 255); N1s (1 <= N1s <= 8) 与本段篱笆的一端所相邻的篱笆的数量; and N2s 与本段篱笆的另一端所相邻的篱笆的数量. (1 <= N2s <= 8).

每组信息的的第 2 行有 N1s 个整数, 分别描述与本段篱笆的一端所相邻的篱笆的标号.

每组信息的的第 3行有 N2s个整数, 分别描述与本段篱笆的另一端所相邻的篱笆的标号.

SAMPLE INPUT (file fence6.in)

text

OUTPUT FORMAT

输出的内容为单独的一行,用一个整数来表示最小的周长.

SAMPLE OUTPUT (file fence6.out)

text

usaco-4.1.3 篱笆回路

目录

形式化题目

正解

思路

代码

复杂度

总结