当前位置：首页 > 提高组 > 2020年NOIP提高组“排水系统”题解（洛谷P7113）：拓扑排序与分数分配的图论算法

2020年NOIP提高组“排水系统”题解（洛谷P7113）：拓扑排序与分数分配的图论算法

5个月前 (07-02)

一、题目解读

2020年NOIP提高组“排水系统”（洛谷P7113）是一道典型的图论问题，要求解决流量分配问题。题目中给定一个有向图，节点表示排水点，边表示管道连接，每个节点有出度（排水方向）。需计算每个节点分配到的流量，确保所有水流最终汇聚到汇点（出度为0的节点）。题目难点在于如何处理分数形式的流量分配，并保证结果化简为最简分数。

二、解题思路

采用拓扑排序结合分数类（Fraction）的解题策略：

1. 拓扑排序：利用入度为零的节点作为起点，通过BFS逐层推进，确保每个节点仅在其所有前驱节点处理完后被访问。

2. 分数分配：自定义分数类支持加法、除法及化简，避免分数运算中的精度问题。

3. 流量计算：对于每个出度不为零的节点，将其流量均分给子节点，通过拓扑排序层层传递，最终汇聚到汇点。

三、解题步骤

1. 建图与度数统计：读入节点数n、汇点数m，构建邻接表adj，记录出度out_degree和入度in_degree。

2. 初始化汇点流量：将每个汇点m的流量设为1/1，加入队列。

3. 拓扑排序处理：

取出队首节点u，若u无出度则跳过（已处理完毕）。

计算均分流量split = flow[u] / out_degree[u]（分数除法）。

遍历u的子节点v，更新flow[v] += split，并减v的入度，若入度为0则加入队列。

4. 输出结果：遍历所有节点，输出化简后的流量分数。

四、代码与注释

#include <iostream>
#include <vector>
#include <queue>
#include <numeric>
using namespace std;

// 自定义分数类，支持化简、加法、除法
struct Fraction {
    long long 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)); // 求GCD
        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);
    }
    
    // 辅助函数：递归求GCD
    static long long gcd(long long a, long long b) {
        return b? gcd(b, a % b) : a;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 加快IO速度
    
    int n, m;
    cin >> n >> m; // 读入节点数n、汇点数m
    
    vector<vector<int>> adj(n+1); // 邻接表
    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]]++; // 子节点入度+1
        }
    }
    
    vector<Fraction> flow(n+1); // 各节点流量
    queue<int> q; // 拓扑排序队列
    
    // 初始化汇点流量
    for (int i = 1; i <= m; ++i) {
        flow[i] = Fraction(1, 1); // 流量初始为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) { // 若v入度为0，加入队列
                q.push(v);
            }
        }
    }
    
    // 输出结果
    for (int i = 1; i <= n; ++i) {
        if (out_degree[i] == 0) {
            // 此处原代码可能缺失输出逻辑，需补全（如cout << flow[i] << "\n";）
        }
    }
}