[NOIP2020] 排水系统

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

在 DAG 上按拓扑序传播精确分数流量，每个点把当前污水均分给所有出边，最后统计所有汇点的分数结果。

OJ: luogu

题目 ID: P7113

难度:普及+/提高

标签:图论拓扑排序数学模拟

日期: 2026-06-19 23:32

题意

这题给了一张没有环的有向图。

前 m 个点是污水接收口，每个点一开始各有 1 吨污水
每个点会把自己当前的污水平均分给所有出边
没有出边的点就是最终排水口

要求输出每个最终排水口最后流出的污水量，而且必须用最简分数表示。

样例图

这张图展示样例中的排水关系：

digraph G {
  rankdir=LR;
  1 -> 2;
  1 -> 3;
  1 -> 5;
  2 -> 4;
  2 -> 5;
  3 -> 5;
  3 -> 4;
}

1 号点先把 1 吨水均分成三份，分别流向 2,3,5。其中流到 2 和 3 的水还会继续被均分一次，所以最后 4 收到 1/3，5 收到 2/3。因为题目要求精确输出，所以这里不能用浮点数近似，必须直接维护分数。

思路

先看一个最直接的小数据暴力：

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// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;

struct Fraction {
    long long num, den;

    Fraction(long long numerator = 0, long long denominator = 1) {
        num = numerator;
        den = denominator;
        normalize();
    }

    void normalize() {
        if (den < 0) {
            num = -num;
            den = -den;
        }
        long long g = std::gcd(llabs(num), llabs(den));
        if (g != 0) {
            num /= g;
            den /= g;
        }
    }
};

Fraction operator+(const Fraction &a, const Fraction &b) {
    __int128 numerator = (__int128) a.num * b.den + (__int128) b.num * a.den;
    __int128 denominator = (__int128) a.den * b.den;
    return Fraction((long long) numerator, (long long) denominator);
}

Fraction operator/(const Fraction &a, long long x) {
    return Fraction(a.num, a.den * x);
}

int n, m;
vector<int> graph[MAXN];
int outdeg[MAXN];
Fraction ans[MAXN]; // ans[i] : 最终流到汇点 i 的污水量

// 直接按题意递归分流。
void dfs(int u, Fraction cur) {
    if (outdeg[u] == 0) {
        ans[u] = ans[u] + cur;
        return;
    }

    Fraction each = cur / outdeg[u];
    for (int v : graph[u]) {
        dfs(v, each);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        graph[i].clear();
        ans[i] = Fraction(0, 1);

        int d;
        cin >> d;
        outdeg[i] = d;
        for (int j = 1; j <= d; j++) {
            int v;
            cin >> v;
            graph[i].push_back(v);
        }
    }

    for (int i = 1; i <= m; i++) {
        dfs(i, Fraction(1, 1));
    }

    for (int i = 1; i <= n; i++) {
        if (outdeg[i] == 0) {
            cout << ans[i].num << ' ' << ans[i].den << '\n';
        }
    }

    return 0;
}

这个暴力完全按题意递归分流：

当前来到点 u，手里有 cur 吨污水
如果 u 是汇点，就把 cur 加到答案里
否则把 cur 平均分成 outdeg[u] 份，递归流向每个后继

这个写法很直观，但如果图很大、路径很多，就会重复遍历很多公共后缀。

题目已经保证整张图是 DAG，所以更高效的办法是按拓扑序传播流量。

做法如下：

用分数 num / den 精确保存每个点当前累计到的污水量。
前 m 个接收口初始都设成 1/1。
求整张图的拓扑序。
按拓扑序处理每个点 u：
- 如果 u 不是汇点，就把 water[u] 均分成 outdeg[u] 份
- 每个后继 v 都加上这一份
最后所有出度为 0 的点就是答案。

这里用到的关键实现是一个简单分数类：

加法时通分再约分
除以整数时直接把分母乘上这个整数

代码结构上和你算法书里的拓扑模板保持一致：先建图和统计入度，再用队列按拓扑序顺推。

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

struct Fraction {
    long long num, den;

    Fraction(long long numerator = 0, long long denominator = 1) {
        num = numerator;
        den = denominator;
        normalize();
    }

    void normalize() {
        if (den < 0) {
            num = -num;
            den = -den;
        }
        long long g = std::gcd(llabs(num), llabs(den));
        if (g != 0) {
            num /= g;
            den /= g;
        }
    }
};

Fraction operator+(const Fraction &a, const Fraction &b) {
    __int128 numerator = (__int128) a.num * b.den + (__int128) b.num * a.den;
    __int128 denominator = (__int128) a.den * b.den;
    return Fraction((long long) numerator, (long long) denominator);
}

Fraction operator/(const Fraction &a, long long x) {
    return Fraction(a.num, a.den * x);
}

int n, m;
vector<int> graph[MAXN];
int indeg[MAXN];
int outdeg[MAXN];
Fraction water[MAXN]; // water[i] : 当前流到结点 i 的总污水量

void read_input() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        graph[i].clear();
        indeg[i] = 0;
        outdeg[i] = 0;
        water[i] = Fraction(0, 1);
    }

    for (int i = 1; i <= n; i++) {
        int d;
        cin >> d;
        outdeg[i] = d;
        for (int j = 1; j <= d; j++) {
            int v;
            cin >> v;
            graph[i].push_back(v);
            indeg[v]++;
        }
    }

    for (int i = 1; i <= m; i++) {
        water[i] = Fraction(1, 1);
    }
}

void solve() {
    queue<int> q;
    int deg[MAXN];
    memcpy(deg, indeg, sizeof(indeg));

    for (int i = 1; i <= n; i++) {
        if (deg[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        if (outdeg[u] > 0) {
            Fraction each = water[u] / outdeg[u];
            for (int v : graph[u]) {
                water[v] = water[v] + each;
                deg[v]--;
                if (deg[v] == 0) {
                    q.push(v);
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    for (int i = 1; i <= n; i++) {
        if (outdeg[i] == 0) {
            cout << water[i].num << ' ' << water[i].den << '\n';
        }
    }

    return 0;
}

复杂度

设点数为 n，边数为 E。

拓扑排序扫描每个点、每条边各一次，复杂度 $O(n + E)$
每次分数运算都只做常数次 gcd

总时间复杂度 $O(n + E)$ ，空间复杂度 $O(n + E)$ 。

总结

这题本质是 DAG 上的流量传播。识别出“无环 + 每条边均分”以后，直接按拓扑序把分数往后推即可。真正容易错的点只有一个：一定要用精确分数，不能用 double。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P7113 [NOIP2020] 排水系统

题目描述

对于一个城市来说，排水系统是极其重要的一个部分。

有一天，小 C 拿到了某座城市排水系统的设计图。排水系统由 $n$ 个排水结点（它们从 $1 \sim n$ 编号）和若干个单向排水管道构成。每一个排水结点有若干个管道用于汇集其他排水结点的污水（简称为该结点的汇集管道），也有若干个管道向其他的排水结点排出污水（简称为该结点的排出管道）。

排水系统的结点中有 $m$ 个污水接收口，它们的编号分别为 $1, 2, \ldots , m$ ，污水只能从这些接收口流入排水系统，并且这些结点没有汇集管道。排水系统中还有若干个最终排水口，它们将污水运送到污水处理厂，没有排出管道的结点便可视为一个最终排水口。

现在各个污水接收口分别都接收了 $1$ 吨污水，污水进入每个结点后，会均等地从当前结点的每一个排出管道流向其他排水结点，而最终排水口将把污水排出系统。

现在小 C 想知道，在该城市的排水系统中，每个最终排水口会排出多少污水。该城市的排水系统设计科学，管道不会形成回路，即不会发生污水形成环流的情况。

输入格式

第一个两个用单个空格分隔的整数 $n, m$ 。分别表示排水结点数与接收口数量。
接下来 $n$ 行，第 $i$ 行用于描述结点 $i$ 的所有排出管道。其中每行第一个整数 $d_i$ 表示其排出管道的数量，接下来 $d_i$ 个用单个空格分隔的整数 $a_1, a_2, \ldots , a_{d_i}$ 依次表示管道的目标排水结点。
保证不会出现两条起始结点与目标结点均相同的管道。

输出格式

输出若干行，按照编号从小到大的顺序，给出每个最终排水口排出的污水体积。其中体积使用分数形式进行输出，即每行输出两个用单个空格分隔的整数 $p$ ， $q$ ，表示排出的污水体积为 $\frac{p}{q}$ 。要求 $p$ 与 $q$ 互素， $q = 1$ 时也需要输出 $q$ 。

输入输出样例 #1

输入 #1

text

输出 #1

text

1
21 3
2 3

输入输出样例 #2

输入 #2

text

1见附件中的 water/water2.in

输出 #2

text

1见附件中的 water/water2.ans

输入输出样例 #3

输入 #3

text

1见附件中的 water/water3.in

输出 #3

text

1见附件中的 water/water3.ans

说明/提示

【样例 #1 解释】

$1$ 号结点是接收口， $4, 5$ 号结点没有排出管道，因此是最终排水口。
$1$ 吨污水流入 $1$ 号结点后，均等地流向 $2, 3, 5$ 号结点，三个结点各流入 $\frac{1}{3}$ 吨污水。
$2$ 号结点流入的 $\frac{1}{3}$ 吨污水将均等地流向 $4, 5$ 号结点，两结点各流入 $\frac{1}{6}$ 吨污水。
$3$ 号结点流入的 $\frac{1}{3}$ 吨污水将均等地流向 $4, 5$ 号结点，两结点各流入 $\frac{1}{6}$ 吨污水。
最终， $4$ 号结点排出 $\frac{1}{6} + \frac{1}{6} = \frac{1}{3}$ 吨污水， $5$ 号结点排出 $\frac{1}{3} + \frac{1}{6} + \frac{1}{6} = \frac{2}{3}$ 吨污水。

【数据范围】

测试点编号	$n \le$	$m \le$
$1 \sim 3$	$10$	$1$
$4 \sim 6$	${10}^3$	$1$
$7 \sim 8$	${10}^5$	$1$
$9 \sim 10$	${10}^5$	$10$

对于全部的测试点，保证 $1 \le n \le {10}^5$ ， $1 \le m \le 10$ ， $0 \le d_i \le 5$ 。

数据保证，污水在从一个接收口流向一个最终排水口的过程中，不会经过超过 $10$ 个中间排水结点（即接收口和最终排水口不算在内）。

[NOIP2020] 排水系统

目录

题意

样例图

思路

代码

复杂度

总结

一图流解析