题解 NOIP2020 T1 排水系统
题解 NOIP2020 T1 排水系统
带 gcd 的纯模拟。（ gcd 就是求最大公约数）
gcd 用来处理分数相加时的分母通分和分数的约分，
通过 gcd 珂以求出 lcm （最小公倍数）：
lcm(x,y)=x×ygcd(x,y)
开个结构体存分数，然后就珂以愉快地拓扑排序了。
最后几个点 WA 是因为 long long 不够用，
开个 __int128 就能过了。
考场上就乖乖写高精吧（逃
代码：
#include<iostream>#include<cstdio>#include<cctype>#include<cstring>#include<queue>#include<cmath>#include<algorithm>#define Rei register int#define ll __int128 //注意是两个下划线！using namespace std;template<typename T>inline void read(T &x) {
x=0; char f=0,c; while(c=getchar(),!isdigit(c)) if(c=='-') f=1; if(f) while(isdigit(c)) x=x*10-c+48,c=getchar(); else while(isdigit(c)) x=x*10+c-48,c=getchar();
}void write(__int128 x) { //__int128需要手写输入输出
if(x/10) write(x/10); putchar(x%10+'0');
}inline ll gcd(ll x,ll y) { //辗转相除法求gcd
ll t; while(y) t=x%y,x=y,y=t; return x;
}const int N=1e5+2;int n,m,cnt,rbq,son;int h[N],rd[N],d[N];struct node {
int next,to;
node(int next=0,int to=0) { this->next=next,this->to=to;
}
} b[N*5];struct fenshu {
ll fenzi,fenmu;
fenshu(ll fenzi=0,ll fenmu=1) { //注意分母不能为0
this->fenzi=fenzi,this->fenmu=fenmu;
}
void huajian() { //分数的化简
ll g=gcd(fenzi,fenmu);
fenzi/=g,fenmu/=g;
}
} O2[N];fenshu jia(fenshu x,fenshu y) { //这里自己推一下就懂了
ll g=gcd(x.fenmu,y.fenmu);
ll k1=y.fenmu/g,k2=x.fenmu/g; return fenshu(x.fenzi*k1+y.fenzi*k2,x.fenmu*k1);
}inline void link(int u,int v) {
b[++cnt]=node(h[u],v),h[u]=cnt,++rd[v];
}queue<int> q;vector<int> ans;void tuopu() { //拓扑排序
for(Rei i=1; i<=n; ++i) { if(!rd[i]) {
q.push(i);
O2[i]=fenshu(1,1);
}
} while(!q.empty()) {
rbq=q.front(),q.pop(); if(!d[rbq]) {
ans.push_back(rbq); continue;
}
O2[rbq].fenmu*=d[rbq]; //水分流
O2[rbq].huajian(); for(Rei i=h[rbq]; i; i=b[i].next) {
--rd[son=b[i].to];
O2[son]=jia(O2[son],O2[rbq]);
O2[son].huajian(); if(!rd[son]) {
q.push(son);
}
}
}
}int main() {
read(n),read(m); for(Rei i=1; i<=n; ++i) {
read(d[i]); for(Rei j=1; j<=d[i]; ++j) {
read(rbq),link(i,rbq);
}
}
tuopu();
sort(ans.begin(),ans.end()); for(int i=0; i<ans.size(); ++i) {
write(O2[ans[i]].fenzi),putchar(' ');
write(O2[ans[i]].fenmu),putchar('\n');
} return 0;
}第一次写题解，请多包涵。