Description

题目链接

Solution

如果不用高精度的话,还是一道很好的题目的。

由于管道不会构成环,原图其实是个 DAG。

然后按照题意拓扑排序即可,需要实现一个分数类(我去年为什么没想到?)。

去年没有更新评测环境,于是只能手写高精度或者预处理 $2, 3, 5$ 的公倍数,现在有了 __int128 用了。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

struct Frac {
    __int128 a, b;
    friend Frac operator + (const Frac &a, const Frac &b) {
         Frac c;
         if (a.b == 0)    return b;
         if (b.b == 0)    return a;
         __int128 g = std::__gcd(a.b, b.b);
         c.b = a.b / g * b.b;
         c.a = b.b / g * a.a + a.b / g * b.a;
         g = std::__gcd(c.a, c.b);
         c.a /= g, c.b /= g;
         return c; 
    }
} f[100010];

std::queue<int> q;
std::vector<int> g[100010];
int in[100010], out[100010];
int n, m;

void write(__int128 x) {
    if (x > 9)    write(x / 10);
    putchar(x % 10 + '0');
}

int main() {
    read(n), read(m);
    for (int i = 1, d; i <= n; ++i) {
        read(d);
        for (int j = 1, v; j <= d; ++j) {
            read(v);
            ++in[v];
            ++out[i];
            g[i].push_back(v);
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (!in[i]) {
            f[i].a = f[i].b = 1;
            q.push(i);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto i : g[u]) {
            Frac tmp = f[u];
            __int128 siz = g[u].size();
            __int128 g = std::__gcd(siz, tmp.a);
            tmp.a /= g;
            siz /= g;
            tmp.b = tmp.b * siz;
            f[i] = f[i] + tmp;
            --in[i];
            if (!in[i])    q.push(i);
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (!out[i]) {
            write(f[i].a);
            putchar(' ');
            write(f[i].b);
            puts("");
        }
    }
    return 0;
}
Last modification:November 18th, 2021 at 11:07 pm