题目链接
洛谷
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;
}
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++) {
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;
}
|