题解 P7113 【排水系统】

· · 题解

NOIP 2020 唯一会做的题……

本题解使用 __int128 来代替高精度

首先我们应该实现的是分数的加法，这里注意要随时除 gcd 来保持分母分子互质。

struct node {
    ll p, q;
    node() {
        p = 0, q = 1;
    }
    node operator *(const ll &rhs) const {
        node res;
        res.p = p, res.q = q * rhs;
        ll g = gcd(res.p, res.q);
        res.p /= g, res.q /= g;
        return res;
    }
    node operator +(const node &rhs) const {
        node res;
        res.q = lcm(q, rhs.q);
        res.p += p * (res.q / q);
        res.p += rhs.p * (res.q / rhs.q);
        ll g = gcd(res.p, res.q);
        res.p /= g, res.q /= g;
        return res;
    }
}

我们已知了流水的方式，那么我们可以直接在图中进行模拟，可以用 dfs / bfs 来实现。这里我们使用更直观（短）的 dfs 来模拟流水过程，即枚举每一个污水接受口排出的水。

void dfs(int x, node k) {
    val[x] = val[x] + k;
    if (d[x]) k = k * d[x];
    for (int i=head[x]; i; i=e[i].next) {
        const int y = e[i].to;
        dfs(y, k);
    }
}

主函数中这样调用：

for (int i=1; i<=m; i++) dfs(i, base); // base为{1, 1}

我们还有一种做法：

该城市的排水系统设计科学，管道不会形成回路，即不会发生污水形成环流的情况。

这句话保证了整个排水系统一定是一个 DAG 图。

DAG 图我们总是会想到拓扑排序，分析一下就可以发现排水的过程其实就是一个拓扑排序的过程。每到一个点就把它所有出边的点都更新一下就好了。

queue<int> q;
void toposort() {
    for (int i=1; i<=n; i++)
        if (ind[i] == 0)
            q.push(i);
    while(!q.empty()) {
        const int x = q.front();
        q.pop();
        if (d[x]) val[x] = val[x] * d[x];
        for (int i=head[x]; i; i=e[i].next) {
            const int y = e[i].to;
            val[y] = val[y] + val[x];
            if (--ind[y] == 0)
                q.push(y);
        }
    }
}

以下是两种做法的完整代码：

dfs:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
#define ll __int128

const int N = 1e5 + 5, M = 5e5 + 5;
int n, m;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

struct node {
    ll p, q;
    node() {
        p = 0, q = 1;
    }
    node operator *(const ll &rhs) const {
        node res;
        res.p = p, res.q = q * rhs;
        ll g = gcd(res.p, res.q);
        res.p /= g, res.q /= g;
        return res;
    }
    node operator +(const node &rhs) const {
        node res;
        res.q = lcm(q, rhs.q);
        res.p += p * (res.q / q);
        res.p += rhs.p * (res.q / rhs.q);
        ll g = gcd(res.p, res.q);
        res.p /= g, res.q /= g;
        return res;
    }
}val[N], base;
struct Edge {
    int to, next;
} e[M];
int head[N], ecnt, ind[N], d[N];
void addedge(int from, int to) {
    e[++ecnt] = (Edge) { to, head[from] };
    head[from] = ecnt;
    ind[to]++;
}

queue<int> q;
vector<int> ans;

void dfs(int x, node k) {
    val[x] = val[x] + k;
    if (d[x]) k = k * d[x];
    for (int i=head[x]; i; i=e[i].next) {
        const int y = e[i].to;
        dfs(y, k);
    }
}

void print(ll n) {
    if(n > 9) print(n / 10);
    putchar(n % 10 + 48);
}

int main(void) {
    base.p = base.q = 1;
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++) {
        if (i <= m) val[i].p = 1;
        scanf("%d", d + i);
        if (d[i] == 0) ans.push_back(i);
        for (int j=1, v; j<=d[i]; j++) {
            scanf("%d", &v);
            addedge(i, v);
        }
    }
    for (int i=1; i<=m; i++) dfs(i, base);
    for (int i=0; i<ans.size(); i++) print(val[ans[i]].p), putchar(' '), print(val[ans[i]].q), putchar('\n');
    return 0;
}

拓扑：

#include <cstdio>
#include <queue>
using namespace std;
#define ll __int128

const int N = 1e5 + 5, M = 5e5 + 5;
int n, m;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

struct node {
    ll p, q;
    node() {
        p = 0, q = 1;
    }
    node operator *(const ll &rhs) const {
        node res;
        res.p = p, res.q = q * rhs;
        ll g = gcd(res.p, res.q);
        res.p /= g, res.q /= g;
        return res;
    }
    node operator +(const node &rhs) const {
        node res;
        res.q = lcm(q, rhs.q);
        res.p += p * (res.q / q);
        res.p += rhs.p * (res.q / rhs.q);
        ll g = gcd(res.p, res.q);
        res.p /= g, res.q /= g;
        return res;
    }
}val[N];
struct Edge {
    int to, next;
} e[M];
int head[N], ecnt, ind[N], d[N];
void addedge(int from, int to) {
    e[++ecnt] = (Edge) { to, head[from] };
    head[from] = ecnt;
    ind[to]++;
}

queue<int> q;
vector<int> ans;
void toposort() {
    for (int i=1; i<=n; i++)
        if (ind[i] == 0)
            q.push(i);
    while(!q.empty()) {
        const int x = q.front();
        q.pop();
        if (d[x]) val[x] = val[x] * d[x];
        for (int i=head[x]; i; i=e[i].next) {
            const int y = e[i].to;
            val[y] = val[y] + val[x];
            if (--ind[y] == 0)
                q.push(y);
        }
    }
}

void print(ll n) {
    if(n > 9) print(n / 10);
    putchar(n % 10 + 48);
}

int main(void) {
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++) {
        if (i <= m) val[i].p = 1;
        scanf("%d", d + i);
        if (d[i] == 0) ans.push_back(i);
        for (int j=1, v; j<=d[i]; j++) {
            scanf("%d", &v);
            addedge(i, v);
        }
    }
    toposort();
    for (int i=0; i<ans.size(); i++) print(val[ans[i]].p), putchar(' '), print(val[ans[i]].q), putchar('\n');
    return 0;
}