2020年NOIP提高组排水系统（洛谷P7113）：从拓扑排序到分数运算

一、问题背景

2020年NOIP提高组的排水系统题目考察了图论中的拓扑排序和分数运算能力。题目模拟了一个城市排水系统，要求计算最终出水口的水量分配比例。

二、算法核心思路

1. 拓扑排序：处理有向无环图中的节点依赖关系

2. 分数运算：精确处理水量分配的比例关系

3. 广度优先搜索(BFS)：实现拓扑排序的过程

三、代码解析（完整注释版）

#include <iostream>
#include <vector>
#include <queue>
#include <numeric>  // 用于gcd函数
using namespace std;

// 分数结构体：处理精确分数运算
struct Fraction {
    long long p, q; // 分子p，分母q
    
    // 构造函数：初始化分数并自动约分
    Fraction(long long _p = 0, long long _q = 1) : p(_p), q(_q) {
        normalize();
    }
    
    // 分数约分方法
    void normalize() {
        if (q < 0) { p = -p; q = -q; } // 保证分母为正
        long long g = gcd(abs(p), abs(q)); // 计算最大公约数
        p /= g;
        q /= g;
    }
    
    // 重载+运算符：实现分数加法
    Fraction operator+(const Fraction& other) const {
        long long lcm = q / gcd(q, other.q) * other.q; // 计算最小公倍数
        return Fraction(p * (lcm / q) + other.p * (lcm / other.q), lcm);
    }
    
    // 重载/运算符：实现分数除以整数
    Fraction operator/(int d) const {
        return Fraction(p, q * d); // 分母乘以除数
    }
    
    // 静态方法：计算最大公约数（欧几里得算法）
    static long long gcd(long long a, long long b) {
        return b ? gcd(b, a % b) : a;
    }
};

int main() {
    ios::sync_with_stdio(false); // 加速C++输入输出
    cin.tie(nullptr);
    
    int n, m; // n-排水节点总数，m-入水口数量
    cin >> n >> m;
    
    // 图的邻接表表示
    vector<vector<int>> adj(n+1); // 节点编号1~n
    vector<int> out_degree(n+1, 0); // 每个节点的出度
    vector<int> in_degree(n+1, 0); // 每个节点的入度
    
    // 构建图结构
    for (int i = 1; i <= n; ++i) {
        cin >> out_degree[i]; // 读取当前节点的出度
        adj[i].resize(out_degree[i]); // 调整邻接表大小
        for (int j = 0; j < out_degree[i]; ++j) {
            cin >> adj[i][j]; // 读取相邻节点
            in_degree[adj[i][j]]++; // 更新相邻节点的入度
        }
    }
    
    vector<Fraction> flow(n+1); // 每个节点的水流分数
    queue<int> q; // 拓扑排序队列
    
    // 初始化：所有入水口流量设为1/1
    for (int i = 1; i <= m; ++i) {
        flow[i] = Fraction(1, 1);
        q.push(i); // 入水口入队
    }
    
    // 拓扑排序处理流程
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        if (out_degree[u] == 0) continue; // 出水口不处理
        
        Fraction split = flow[u] / out_degree[u]; // 分流计算
        
        // 处理所有相邻节点
        for (int v : adj[u]) {
            flow[v] = flow[v] + split; // 累加流量
            if (--in_degree[v] == 0) { // 入度减1，若为0则入队
                q.push(v);
            }
        }
    }
    
    // 输出所有出水口的结果
    for (int i = 1; i <= n; ++i) {
        if (out_degree[i] == 0) {
            cout << flow[i].p << " " << flow[i].q << "\n";
        }
    }
    
    return 0;
}

四、关键知识点详解

1. 分数运算实现

代码中自定义的Fraction结构体实现了：

• 自动约分功能（normalize方法）

• 分数加法（operator+重载）

• 分数除以整数（operator/重载）

• 最大公约数计算（gcd静态方法）

2. 拓扑排序应用

通过维护入度数组(in_degree)和队列(q)实现：

1. 初始时将入度为0的节点（入水口）入队

2. 处理队列中的节点，将其流量分配给后继节点

3. 后继节点入度减为0时入队

3. 性能优化

• 使用ios::sync_with_stdio(false)加速输入输出

• 使用邻接表存储图结构，空间复杂度O(n+m)

五、常见问题解答

Q: 为什么需要分数运算而不是浮点数？ A: 浮点数存在精度问题，在多次运算后可能产生误差，而分数运算能保证精确性。

Q: 如何处理大数运算？ A: 使用long long类型存储分子分母，注意约分防止溢出。

Q: 为什么使用拓扑排序？ A: 排水系统是有向无环图，拓扑排序能确保按正确顺序处理节点。