[USACO19OPEN] Milk Factory

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

通道忽略方向后是树,有向定向必有终点,答案即出度为 0 的唯一加工站,多于一个就无解。

OJ: roj

题目 ID: 2126

难度:普及-

标签:图论树出度python

创建: 2026-10-08 07:42

更新: 2026-10-08 07:42

形式化题目

给定 NN 个加工站(编号 1…N1 \dots N,1⩽N⩽1001 \leqslant N \leqslant 100)和 N−1N-1 条单向传送带,第 kk 条为 ak→bka_k \to b_k。题面括号说明这些通道是用「最小数量」把所有站连起来的,即忽略方向后 GG 的底图是一棵有 NN 个点、N−1N-1 条边的连通无环树。

定义可达关系 u→∗vu \to^* v 为存在从 uu 到 vv 的有向路径(u→∗uu \to^* u 恒成立,空路径)。求最小的 i∈{1,…,N}i \in \{1,\dots,N\},使得对任意 j∈{1,…,N}j \in \{1,\dots,N\} 都有 j→∗ij \to^* i;若不存在这样的 ii,输出 −1-1。

以题面样例为例,N=3N = 3、两条边 1→21 \to 2、3→23 \to 2,站 22 是唯一的汇合点:1→∗21 \to^* 2、3→∗23 \to^* 2、2→∗22 \to^* 2,故答案为 22。

正解

思路

最直接的判定是:反向建图(把 a→ba \to b 存成 b→ab \to a),对每个 ii 从 ii 出发做一次 DFS/BFS 数能反向走到的点数,第一次达到 NN 的 ii 就是答案,全都不行输出 −1-1。复杂度 O(N(N+M))=O(N2)O(N(N+M)) = O(N^2),N⩽100N \leqslant 100 时轻松通过。但它完全没有用到「底图是一棵树」这个约束,而这个约束恰恰能把判定压缩到一次出度统计。

关键在于观察路径的终点:

  • 由于底图是树、边数是 N−1N-1,GG 里不可能出现有向环(有向环要求底图有环)。于是在这个有限的有向无环图上,从任意站 uu 出发顺着出边一直走,路径只可能一路延伸或者停在某个出度为 0 的站,不会绕圈,必然终止。
  • 设 uu 是出度为 0 的站。它没有任何出边,所以从 uu 出发只能到达它自己。若要 u→∗iu \to^* i,就必须 i=ui = u。也就是说:任何出度为 0 的站,一旦答案存在,答案只能是它本身。

两条观察合起来给出充要条件:

出度为 0 的站数 结论
⩾2\geqslant 2 取其中两个 u≠vu \neq v。由上一条,答案存在时须同时有 i=ui = u 与 i=vi = v,矛盾,故输出 −1-1
=1= 1(记为 ii) 从任意 jj 出发的路径必然终止在某个出度为 0 的站,而全图这样的站只有 ii,所以 j→∗ij \to^* i 对一切 jj 成立,ii 就是答案

于是**「答案存在」等价于「出度为 0 的站恰好一个」,且该站即为答案**。值得注意的是答案天然唯一:若两个站 i≠ji \neq j 同时被所有点可达,则 i→∗ji \to^* j 且 j→∗ij \to^* i,在树的有向定向中构成有向环,与边数为 N−1N-1 矛盾。所以「取最小的 ii」在这道题的合法输入下不需要额外处理,升序扫描的第一命中就是唯一解。

细看这条判定为什么必须依赖树性:对一般有向图,「唯一出度为 0 的点」只是必要条件。例如边集 1→3, 2→1, 4→5, 5→41 \to 3,\ 2 \to 1,\ 4 \to 5,\ 5 \to 4:出度为 0 的站只有 33,但站 4,54,5 构成的底图环根本无法到达 33。本题的输入保证排除了这种情形(题面保证 N−1N-1 条通道连通所有站)。若想对任意有向图都稳妥,可以退回上面 O(N2)O(N^2) 的反图 DFS 逐点验证——但本题的数据生成脚本已断言每一组数据都是树。

代码

python
#!/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-08 07:42
# update_at: 2026-10-08 07:42

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    # 通道忽略方向是最少的 N-1 条 ⇒ 底图是树,有向定向不可能有环,
    # 每个站顺着出边走必然停在出度为 0 的站(sink)。
    edges = [(next(data), next(data)) for _ in range(n - 1)]
    sinks = set(range(1, n + 1)) - {start for start, _end in edges}  # 出度为 0 的站
    sink_count = len(sinks)
    # sink 多于一个 ⇒ 谁也到不了别的 sink;恰好一个 ⇒ 全图都汇入它,它即答案
    print(min(sinks) if sink_count == 1 else -1)


if __name__ == "__main__":
    solve()
cpp
/**
 * 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-08 07:42
 * update_at: 2026-10-08 07:42
 */

// [USACO19OPEN] Milk Factory
// 题意:N 个加工站、N-1 条单向传送带 a -> b,且这些通道是用最少数量把所有站连起来的,
//       所以忽略方向后是一棵连通无环的树。求最小的 i,使得从其他每个站出发沿单向边
//       (可经过中间站)都能到达 i;不存在则输出 -1。
// 做法:树的有向定向不可能出现有向环,所以从任意站顺着出边一直走必然停在某个出度为 0
//       的站(sink)。若出度为 0 的站超过 1 个,任何一个 sink 都到不了别的 sink,无解;
//       若恰好一个,则所有站的路径都只能终止于它,它就是答案。故答案 = 唯一的 sink。
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 105;
int out_degree[MAXN]; // out_degree[i]:从 i 出发的传送带条数

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0; // 保证 1 <= N <= 100

    for (int k = 1; k <= n - 1; ++k) {
        int a, b;
        scanf("%d %d", &a, &b); // 传送带 a -> b,只有出发站 a 的出度增加
        out_degree[a]++;
    }

    int sink_count = 0; // 出度为 0 的站(路径终点)个数
    int answer = -1;
    for (int i = 1; i <= n; ++i) { // 升序扫描,顺便保证答案取最小
        if (out_degree[i] == 0) {
            sink_count++;
            answer = i;
        }
    }

    if (sink_count == 1) {
        printf("%d\n", answer);
    } else {
        printf("-1\n");
    }
    return 0;
}

复杂度

时间 O(N)O(N):读入 N−1N-1 条边时顺带累加出发站出度,再线性扫一遍 1…N1 \dots N 统计出度为 0 的站。空间 O(N)O(N),只有一个出度数组。N=100N = 100 时总操作数不到 300300 次,远低于 1000 ms 时限。

总结

这道题的关键不是「可达性」,而是「可达性在树的有向定向下退化成什么」。有向环不存在,所以每条路都有终点;终点的出度为 0,所以终点只能是自己;出度为 0 的站一旦多于一个就谁也到不了谁。三步推理把 O(N2)O(N^2) 的反图搜索压缩成一次出度统计,也解释了答案为什么必然唯一——同一条「无环」性质既保证了判定充分、又保证了「最小」这一要求不会真的起作用。

实现上的两个坑:一是边的方向,输入「从 aia_i 到 bib_i」增加的是 aia_i 的出度而非 bib_i;二是 N=1N = 1 的退化情形,没有通道,站 1 出度为 0 且是全图唯一的 sink,答案 11,与「其他加工站集合为空、条件真空成立」的理解一致,算法天然覆盖。

数据说明:本题素材由带数据生成脚本的仓库提供(10 组数据由脚本按分层结构构造,非 USACO 官方数据),题面为网络重建版本。生成脚本断言每组数据的底图都是树,本解法的成立依赖该性质。