[NOIP2020] 排水系统

题目链接

洛谷

LOJ

题目分析

注意到,「污水接收口」实际上就是入度为 0 的点,「最终排水口」实际上就是出度为 0 的点。污水先从「污水接收口」流出,然后就与「污水接收口」无关了,而流入某个点的先后顺序与结果无关,并且数据保证为有向无环图,所以可以使用拓扑排序。

本题的另一个要点是分数的处理,注意在分数相加的时候数字太大会超出 long long 甚至 unsigned long long 的范围,我们需要使用高精度或 __int128, 由于高精度较为复杂,下面的代码实现使用了 __int128

代码实现

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

typedef __int128 bint;

const int MAXN = 100010;

struct Number {
bint p, q;

/* 约分 */
void simplify()
{
if (p == 0) return;
bint g = __gcd(p, q);
p /= g;
q /= g;
}

Number()
{
p = 0, q = 1;
}
};

int n, m;
int cnt[MAXN];
int deg[MAXN];
Number w[MAXN];
vector<int> G[MAXN];

/* 分数相加 */
const Number operator+(const Number a, const Number b)
{
Number tmp;
bint g = __gcd(a.q, b.q);
tmp.q = a.q / g * b.q;
tmp.p = tmp.q / a.q * a.p + tmp.q / b.q * b.p;
tmp.simplify();
return tmp;
}

/* 用于输出 __int128 */
void write(bint x)
{
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}

int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> cnt[i];
for (int j = 1; j <= cnt[i]; j++) {
int to;
cin >> to;
G[i].push_back(to);
deg[to]++;
}
}

queue<int> q;
for (int i = 1; i <= m; i++) {
//对于每个污水接收口,初始化污水为 1 吨
w[i].p = w[i].q = 1;
q.push(i);
}
while (!q.empty()) {
int x = q.front();
q.pop();

// 得到每根管道分得的污水量
Number now = w[x];
bint g = __gcd(bint(cnt[x]), now.p);
now.p /= g;
now.q *= cnt[x] / g;

for (auto to : G[x]) {
deg[to]--;
if (deg[to] == 0) {
q.push(to);
}

// 排出污水,进行累加
w[to] = now + w[to];
}
}

for (int i = 1; i <= n; i++) {
if (cnt[i] == 0) {
w[i].simplify();
write(w[i].p);
putchar(' ');
write(w[i].q);
putchar('\n');
}
}
return 0;
}

[NOIP2020] 排水系统
http://xiao-h.com/2023/09/27/NOIP2020-排水系统/
作者
小H
发布于
2023年9月27日
许可协议