NOIP2020ST1 排水系统 解题思路报告

声明:

1. 本题是NOIP2020提高组T1
2. 代码是我写的，解释和注释是AI(chatgpt-o1-mini)写的。
3. 因为我喜欢把题目讲的比较清楚，但是又懒(🤣)

一、问题理解

题目概述

在这道题目中，我们需要模拟一个城市的排水系统，并计算每个最终排水口将排出的污水体积。排水系统由若干排水结点和单向排水管道构成。具体要求如下：

1. 排水结点：共有 n 个排水结点，编号从 1 到 n。
2. 接收口：前 m 个结点是污水接收口，每个接收口接收 1 吨污水。
3. 排出管道：每个结点可能有若干条单向排出管道，指向其他结点。
4. 最终排水口：没有排出管道的结点被视为最终排水口，将污水排出系统。
5. 污水分配：每个结点接收到的污水均等分配到所有排出管道，最终排水口将收到并排出相应的污水。

最终需要输出每个最终排水口排出的污水体积，以最简分数形式表示。

关键点

1. 有向无环图（DAG）：排水系统中的管道不会形成回路，保证了整体结构为有向无环图。
2. 拓扑排序：由于系统是DAG，可以使用拓扑排序来处理污水的流动。
3. 分数运算：污水量需要以分数形式表示，并保持最简分数，避免精度丢失。

二、解题思路

1. 数据结构与变量定义

• 邻接表 (adj)：用于存储每个结点的排出管道指向的目标结点。
• 入度数组 (ind)：记录每个结点的入度数，用于拓扑排序。
• 污水量表示 (nds)：使用 pair<__int128, __int128> 表示每个结点的污水量，分子和分母分别存储在 first 和 second。
• 队列 (qu)：用于进行拓扑排序的队列，存储当前入度为0的结点。

2. 初始化

• 接收口：前 m 个结点作为接收口，初始化污水量为 1/1。
• 其他结点：初始化污水量为 0/1。
• 构建图结构：根据输入构建邻接表，并统计每个结点的入度。

3. 分数运算函数

由于需要处理分数的加法和约分，定义如下辅助函数：

• 最大公约数 (gcd128)：计算两个 __int128 数的最大公约数，用于分数约分。
• 分数简化 (sf)：将分数 p/q 简化为最简形式。
• 分数加法 (add)：实现两个分数的加法，并返回结果的最简分数形式。

4. 拓扑排序与污水分配

使用Kahn算法进行拓扑排序，并在排序过程中进行污水的分配：

1. 入度为0的结点入队：所有入度为0的结点（即接收口）首先入队。
2. 处理队列：
   • 弹出队首结点 u。
   • 如果 u 有排出管道，则将其污水量均分到所有目标结点 v：
     • 对于每个目标结点 v，计算从 u 分配到 v 的污水量，即 nds[u] / d_u，其中 d_u 是 u 的排出管道数量。
     • 将分配的污水量加到 v 的当前污水量上，并进行分数简化。
     • 更新 v 的入度，若入度减为0，则将 v 入队。
3. 重复以上步骤，直到队列为空。

5. 输出结果

遍历所有结点，找到没有排出管道的最终排水口，并按结点编号从小到大的顺序输出其污水量，以最简分数的形式输出。

三、代码实现与详细注释

以下是经过详细注释的代码实现：

#include <bits/stdc++.h>
using namespace std;

// 使用 64 位整数类型
using ll = int64_t;

// 使用 128 位整数类型，以防分数计算时溢出
using i128 = __int128;

// 定义最大结点数，根据题目限制
const ll maxn = 1e5 + 5;

// 全局变量定义
ll n, m;                            // n: 排水结点数, m: 接收口数量
ll ind[maxn];                       // 入度数组，ind[i] 表示结点 i 的入度
pair<i128, i128> nds[maxn];        // 污水量数组，nds[i] = {分子, 分母}
vector<ll> adj[maxn];               // 邻接表，存储每个结点的排出管道指向的结点

/**
 * 计算两个 128 位整数的最大公约数
 * 使用欧几里得算法
 */
i128 gcd128(i128 a, i128 b){
    while(b != 0){
        i128 temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

/**
 * 简化分数 p/q 为最简形式
 * 将分子和分母同时除以它们的最大公约数
 */
void simplify_fraction(i128 &p, i128 &q){
    i128 gcd_value = gcd128(p, q);
    p /= gcd_value;
    q /= gcd_value;
}

/**
 * 实现分数加法：p1/q1 + p2/q2
 * 返回结果的最简分数 {p, q}
 */
pair<i128, i128> add_fractions(i128 p1, i128 q1, i128 p2, i128 q2){
    // 先计算两个分数的公共分母，即它们的最小公倍数
    i128 lcm = (q1 * q2) / gcd128(q1, q2);
    
    // 将两个分数通分到相同的分母
    i128 new_p1 = p1 * (lcm / q1);
    i128 new_p2 = p2 * (lcm / q2);
    
    // 分子相加
    i128 sum_p = new_p1 + new_p2;
    i128 sum_q = lcm;
    
    // 简化分数
    simplify_fraction(sum_p, sum_q);
    
    return {sum_p, sum_q};
}

/**
 * 重载 `<<` 操作符以支持输出 __int128 类型
 * 将 __int128 类型转换为字符串后输出
 */
ostream &operator<<(ostream &os, i128 num){
    // 处理负数
    if(num < 0){
        os << '-';
        num = -num;
    }
    
    string s;
    
    // 处理数字为0的情况
    if(num == 0){
        s = "0";
    }
    
    // 逐位提取数字
    while(num > 0){
        char digit = '0' + (num % 10);
        s += digit;
        num /= 10;
    }
    
    // 反转字符串以得到正确的数字顺序
    reverse(s.begin(), s.end());
    
    os << s;
    return os;
}

int main(){
    // 提高 I/O 效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    // 读取结点数 n 和接收口数量 m
    cin >> n >> m;
    
    // 初始化所有结点的污水量
    // 前 m 个结点为接收口，初始污水量为 1/1
    // 其他结点初始污水量为 0/1
    for(ll i = 1; i <= n; i++){
        if(i <= m){
            nds[i] = {1, 1};    // 接收口污水量初始化为 1/1
        }
        else{
            nds[i] = {0, 1};    // 其他结点污水量初始化为 0/1
        }
        
        // 读取当前结点的排出管道数量
        ll d_i;
        cin >> d_i;
        
        // 读取每条排出管道的目标结点，并更新邻接表和入度
        for(ll j = 0; j < d_i; j++){
            ll target;
            cin >> target;
            adj[i].emplace_back(target);   // 记录排出管道
            ind[target]++;                  // 增加目标结点的入度
        }
    }
    
    // 使用队列进行拓扑排序
    queue<ll> qu;
    
    // 将所有入度为0的结点（接收口）加入队列
    for(ll i = 1; i <= n; i++){
        if(ind[i] == 0){
            qu.emplace(i);
        }
    }
    
    // 开始拓扑排序和污水分配
    while(!qu.empty()){
        ll u = qu.front();   // 取出队首结点
        qu.pop();
        
        // 获取当前结点的污水量
        pair<i128, i128> current_water = nds[u];
        
        // 获取当前结点的排出管道数量
        ll d_u = adj[u].size();
        
        // 如果当前结点有排出管道，则将污水均等分配到所有目标结点
        if(d_u > 0){
            // 计算分配给每个目标结点的污水量
            // 分配量为 current_water / d_u，即分子不变，分母乘以 d_u
            pair<i128, i128> distribute = {current_water.first, current_water.second * d_u};
            simplify_fraction(distribute.first, distribute.second);   // 简化分数
            
            // 遍历所有排出管道，分配污水到目标结点
            for(auto &v : adj[u]){
                // 将 distribute 分数加到目标结点 v 的当前污水量上
                nds[v] = add_fractions(nds[v].first, nds[v].second, distribute.first, distribute.second);
                
                // 更新目标结点 v 的入度
                ind[v]--;
                
                // 如果目标结点 v 的入度减为0，则将其加入队列
                if(ind[v] == 0){
                    qu.emplace(v);
                }
            }
        }
        // 如果当前结点没有排出管道，是最终排水口，无需分配污水
    }
    
    // 遍历所有结点，按编号从小到大输出最终排水口的污水量
    for(ll i = 1; i <= n; i++){
        if(adj[i].empty()){    // 判断是否为最终排水口（无排出管道）
            // 输出污水量的分子和分母，以空格分隔
            cout << nds[i].first << ' ' << nds[i].second << '\n';
        }
    }
    
    return 0;
}

代码详细解释

1. 引入必要的库和类型定义：

   • #include <bits/stdc++.h>：引入所有标准库。
   • using ll = int64_t; 和 using i128 = __int128;：定义 ll 为 64 位整数，i128 为 128 位整数，用于处理大数分数。

2. 全局变量和数据结构：

   • maxn：定义最大的结点数量，根据题目的约束（n \leq 10^5）。
   • n, m：分别表示结点总数和接收口数量。
   • ind[maxn]：入度数组，记录每个结点的入度数。
   • nds[maxn]：污水量数组，用 pair<i128, i128> 表示分子和分母。
   • adj[maxn]：邻接表，以向量数组的形式存储每个结点的排出管道指向的结点。

3. 辅助函数：

   • gcd128：使用欧几里得算法计算两个 __int128 数的最大公约数，确保分数能够被正确地约分。
   • simplify_fraction：将分数 p/q 简化为最简形式，即分子和分母同时除以它们的最大公约数。
   • add_fractions：实现分数的加法，返回两个分数相加后的最简分数形式。首先找到两个分数的最小公倍数作为公共分母，然后通分相加，最后进行约分。
   • operator<< 重载：由于 C++ 标准库不支持直接输出 __int128 类型，因此需要重载 << 操作符，将 __int128 类型转换为字符串后输出。

4. 主函数逻辑：

   • I/O 优化：通过 ios::sync_with_stdio(false); 和 cin.tie(nullptr); 提高输入输出效率，避免因频繁的同步导致的性能问题。
   • 输入处理：
     • 读取结点总数 n 和接收口数量 m。
     • 遍历每个结点，初始化其污水量：
       • 如果是接收口（编号 \leq m），则污水量初始化为 1/1。
       • 否则，污水量初始化为 0/1。
     • 读取每个结点的排出管道数量 d_i，并将目标结点添加到邻接表中，同时更新目标结点的入度。
   • 拓扑排序与污水分配：
     • 将所有入度为0的结点（即接收口）加入队列 qu。
     • 当队列不为空时，弹出队首结点 u，并处理其污水分配：
       • 如果 u 有排出管道，则将其污水量均等分配到所有目标结点：
         • 计算分配给每个目标结点的污水量 distribute，即 u 的污水量除以排出管道数量 d_u。
         • 遍历每个目标结点 v，将 distribute 加到 v 的当前污水量上，并更新 v 的入度。
         • 如果 v 的入度减为0，则将其加入队列。
       • 如果 u 没有排出管道，则它是最终排水口，无需进一步处理。
   • 输出结果：
     • 遍历所有结点，从编号 1 到 n：
       • 如果结点 i 没有排出管道（即 adj[i].empty()），则输出其污水量 nds[i].first（分子）和 nds[i].second（分母），以空格分隔，并换行。

四、总结

这道题目通过模拟污水在排水系统中的流动，要求计算每个最终排水口排出的污水量。由于系统中的管道不会形成回路，整个系统可以被视为一个有向无环图（DAG）。因此，可以利用拓扑排序的方法来处理污水的流向。

关键点在于：

1. 分数运算：污水量以分数形式表示，必须处理分数的加法和约分，确保最终结果的正确性和简洁性。
2. 拓扑排序：使用Kahn算法进行拓扑排序，确保按照正确的顺序处理污水分配，避免漏算或重复计算。
3. 高精度计算：由于分子的值可能会非常大，使用 __int128 类型来存储分子和分母，以防止溢出。

通过以上思路和实现，可以高效、准确地计算出每个最终排水口排出的污水量，满足题目的所有要求。