LGP7113 [NOIP 2020] 排水系统 学习笔记
Luogu Link
题意简述
给定一个 \(n\) 个点的 \(\texttt{DAG}\)。我们认为它是一个排水系统。
节点 \(u\) 有 \(d_u\) 条输出管道，污水会被平分成 \(d_u\) 份流向下家节点。特别的，\(d_u=0\) 时认为这个节点直通污水厂，是一个最终排水口。
对于其中 \(1\sim m\) 这些点，它们会接收到 \(1\) 吨污水。保证他们不被任何节点指向。问每个最终排水口会排出多少污水。答案请用最简分数表示。
\(0\le d_u\le 5\)，\(n\le 10^5\)，\(m\le 10\)。保证没有任何一滴水会经过 \(10\) 个以上的中间节点（接收节点和最终排水口不算在内）。
做法解析
拓扑排序即可。
但是这题的数据范围？分母理论上来说可以干到 \(2^{11}\times 3^{11}\times 5^{11}\) 附近。因为水量的绝对数值最多是 \(m=10\)，所以分子理论最高就是 \(30\times 10^{11}\times 10=3\times 10^13\)。按理来说这些还在 long long 范围内啊。但是一般而言，通分的过程是 \(\frac{a}{c}+\frac{b}{d}=\frac{ad+bc}{cd}\)。这一步就爆 long long 了。最简单的解决方法是直接用 __int128，毕竟 long long 范围的两倍就是 __int128 范围。另外实际上由于分母只有若干 \(2,3,5\) 组成，所以你不妨去维护一下分子和分母 \(2,3,5\) 的含量。不过有现成的 __int128 为什么不用呢？
代码实现
#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=1e5+5;
int N,M,X;
vector<int> Gr[MaxN];
int ind[MaxN],oud[MaxN];
void addedge(int u,int v){Gr[u].push_back(v),ind[v]++;}
molo fz[MaxN],fm[MaxN];queue<int> q;
molo agcd(molo x,molo y){return y?agcd(y,x%y):x;}
void solve(){for(int i=1;i<=N;i++)fm[i]=1;for(int i=1;i<=M;i++)fz[i]=1,q.push(i);while(q.size()){int u=q.front();q.pop();if(!oud[u])continue;fm[u]*=oud[u];for(int v : Gr[u]){ind[v]--;fz[v]=fz[u]*fm[v]+fz[v]*fm[u],fm[v]*=fm[u];molo cg=agcd(fz[v],fm[v]);fz[v]/=cg,fm[v]/=cg;if(!ind[v])q.push(v);}}
}
int main(){readis(N,M);for(int i=1;i<=N;i++){readi(oud[i]);for(int j=1;j<=oud[i];j++)readi(X),addedge(i,X);}solve();for(int i=1;i<=N;i++)if(!oud[i])writip(fz[i]),writil(fm[i]);return 0;
}
反思总结
__int128 还是太伟大了。除了在你对它直接套 abs() 的时候。