题解

问题分析

题目要求计算排水系统中每个最终排水口的污水排放量。系统由结点（排水结点）和单向管道组成，形成有向无环图（DAG）：

• 接收口（1~m）为入度0的结点，各初始流入1吨污水；
• 最终排水口为出度0的结点，需输出其累计的污水量（以最简分数表示）；
• 污水在每个结点会平均分配到其所有排出管道，流向下游结点。

核心思路

1. 图结构特性：系统是DAG（无环），污水流动方向唯一，无环流，可通过拓扑排序按顺序处理结点（确保上游结点的污水全部分配后再处理下游结点）。
2. 分数运算：污水量需以分数形式精确计算（避免浮点数误差），需支持分数的加法、除法及约分（通过最大公约数gcd）。
3. 递归处理拓扑序：从入度为0的接收口开始，递归分配污水到下游结点，当下游结点入度减为0时（所有上游污水均已流入），继续处理该结点，直至最终排水口。

算法步骤

1. 数据结构设计：

   • 记录每个结点的排出管道（s[i][j]）及数量（d[i]）；
   • 计算每个结点的入度（in[i]，即汇入管道数量）；
   • 用分数类（frac）存储每个结点的污水量，包含分子（a）、分母（b），并实现加法、除法及约分操作。

2. 初始化：

   • 接收口（1~m）初始污水量为 1/1（ans[i].a=1, ans[i].b=1）；
   • 其他结点初始污水量为 0/1。

3. 拓扑排序处理：

   • 对入度为0的结点（初始为接收口）调用递归函数 get(x)，将其污水平均分配到所有下游结点（s[x][j]）；
   • 分配后，下游结点的入度减1，若入度变为0，递归处理该下游结点（确保所有上游污水均已流入）。

4. 结果输出：

   • 遍历所有结点，输出出度为0（d[i]=0）的结点的污水量（分数形式，分子分母互素）。

分数运算详解

• 约分：通过 gcd 计算分子分母的最大公约数，将分数化简为最简形式（如 2/4 化简为 1/2）。
• 加法：两个分数 a/b 和 c/d 相加，通分后为 (ad + bc)/(bd)，再约分（如 1/3 + 1/6 = (2 + 1)/6 = 3/6 = 1/2）。
• 除法：分数 a/b 除以整数 k，等价于乘以 1/k，即 a/(b*k)，再约分（如 1/3 ÷ 2 = 1/(3*2) = 1/6）。

代码实现解析

1. 分数类（frac）：

   • 成员 a（分子）、b（分母），构造函数初始化分数为 x/y（默认 0/1）。
   • 重载 + 实现分数加法，/ 实现分数除以整数，均自动约分。
   • prints() 函数输出分数（分子分母，用 __int128 支持大整数输出）。

2. 拓扑处理（get 函数）：

   • 对当前结点 x，将其污水量平均分配到所有下游结点 s[x][j]（即 ans[s[x][j]] += ans[x] / d[x]）。
   • 下游结点入度减1，若入度为0，递归处理该结点（确保按拓扑序处理）。

3. 主逻辑：

   • 读取输入，记录排出管道和入度。
   • 初始化接收口污水量，对入度为0的结点启动拓扑处理。
   • 输出所有出度为0的结点的污水量。

复杂度分析

• 时间复杂度：O(n + E)，其中 n 为结点数，E 为总边数（管道数）。每个结点和边仅处理一次，分数运算为常数级（因 d[i] ≤ 5，运算规模可控）。
• 空间复杂度：O(n + E)，用于存储结点信息、入度、分数数据等。

示例说明（样例1）

• 结点1（接收口）有3个排出管道（2、3、5），初始污水 1/1，分配后2、3、5各得 1/3。
• 结点2有2个排出管道（4、5），1/3 分配后4、5各得 1/6。
• 结点3有2个排出管道（5、4），1/3 分配后5、4各得 1/6。
• 最终排水口4的总污水：1/6 + 1/6 = 1/3；排水口5的总污水：1/3 + 1/6 + 1/6 = 2/3，与输出一致。

#include <cstdio>
using namespace std;
int n, m, d[110000], s[110000][10], in[110000], bj[110000], i, j;
__int128 gcd(__int128 a, __int128 b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
void print(__int128 x) {
    if (x < 10)
        printf("%d", int(x));
    else {
        print(x / 10);
        printf("%d", int(x % 10));
    }
}
class frac {
public:
    __int128 a, b;
    frac(__int128 x = 0, __int128 y = 1): a(x), b(y) {}
    frac(const frac &x): a(x.a), b(x.b) {}
    frac &operator = (frac x) {
        this->a = x.a;
        this->b = x.b;
        return *this;
    }
    frac operator / (int x) const {
        frac c = *this;
        __int128 s = gcd(x, c.a);
        c.b = x / s * c.b;
        c.a = c.a / s;
        return c;
    }
    frac operator + (frac x) const {
        frac c;
        __int128 s = gcd(this->b, x.b);
        c.a = x.b / s * this->a + this->b / s * x.a;
        c.b = this->b / s * x.b;
        s = gcd(c.a, c.b);
        c.a = c.a / s;
        c.b = c.b / s;
        return c;
    }
    void prints() const {
        print(this->a);
        printf(" ");
        print(this->b);
    }
} ans[110000];
void get(int x) {
    int i;

    for (i = 1; i <= d[x]; i++) {
        ans[s[x][i]] = ans[s[x][i]] + ans[x] / d[x];
        in[s[x][i]]--;

        if (in[s[x][i]] == 0)
            get(s[x][i]);
    }
}
main() {
    //freopen("water.in", "r", stdin);
    //freopen("water.out", "w", stdout);
    scanf("%d%d", &n, &m);

    for (i = 1; i <= n; i++) {
        scanf("%d", &d[i]);

        for (j = 1; j <= d[i]; j++) {
            scanf("%d", &s[i][j]);
            in[s[i][j]]++;
        }
    }

    for (i = 1; i <= m; i++)
        ans[i].a = 1;

    for (i = n; i >= 1; i--)
        if (bj[i] == 0 && in[i] == 0)
            get(i);

    for (i = 1; i <= n; i++)
        if (d[i] == 0) {
            ans[i].prints();
            printf("\n");
        }
}