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