对于一个城市来说，排水系统是极其重要的一个部分。
有一天，小 C 拿到了某座城市排水系统的设计图。排水系统由 nn 个排水结点（它们从 1 sim n1∼n 编号）和若干个单向排水管道构成。每一个排水结点有若干个管道用于汇集其他排水结点的污水（简称为该结点的汇集管道），也有若干个管道向其他的排水结点排出污水（简称为该结点的排出管道）。
排水系统的结点中有 mm 个污水接收口，它们的编号分别为 1, 2, ldots , m1,2,…,m，污水只能从这些接收口流入排水系统，并且这些结点没有汇集管道。排水系统中还有若干个最终排水口，它们将污水运送到污水处理厂，没有排出管道的结点便可视为一个最终排水口。
现在各个污水接收口分别都接收了 11 吨污水，污水进入每个结点后，会均等地从当前结点的每一个排出管道流向其他排水结点，而最终排水口将把污水排出系统。
现在小 C 想知道，在该城市的排水系统中，每个最终排水口会排出多少污水。该城市的排水系统设计科学，管道不会形成回路，即不会发生污水形成环流的情况。
link

题意

题面非常简洁了

给出一张无环图和$m$个源点，每个源点有$1$单位的水，每次会平均分给几个点，求几个终点最后的结果是多少。

思路

直接对于每个源点跑dfs统计答案，管它什么拓扑呢非常的暴力。

但是呢洛谷构造的数据卡掉了unsigned long long，所以我们换成__int128（比赛不能用）

这里写一点比赛的小技巧：

如果不会写gcd，可以去algorithm头文件里找到__gcd()(dev的话可以写了头文件然后直接ctrl+左键)，然后抄出来，那个代码逻辑还是勉强可以看懂的，大概像这样：

ll gcd(ll m,ll n){
    while(n!=0){
        ll t=m%n;
        m=n,n=t;
    }
    return m;
}

有了gcd，那么化简分数和分数加法就很简单了，注意显然$\text{lcm}(a,b) =ab \div \gcd(a,b)$

其他注意的细节和思路可见代码注释

代码

#include<bits/stdc++.h>
#define int __int128
//要开__int128
using namespace std;
inline unsigned int read(){//int128没有cin，所以要写快读
    unsigned int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void print(unsigned int x){//输出也一样
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
}
int gcd(int m,int n){//从algorihm里抄来的gcd
    while(n!=0){//是个辗转相除的循环写法
        int t=m%n;
        m=n,n=t;
    }
    return m;
}
vector<int> t[100005];//vector存图
int n,m;
struct fra{//fraction，分数
    int m,s;//m是分母，s是分子
    void cle(){//初始化函数
        m=0,s=0;
    }
}res[100005],a[100005];
fra ad(fra a,fra b){//将两个分数相加
    if(a.m==0) return b;//避免除以0
    fra ans;
    int gb=a.m*b.m/gcd(a.m,b.m);//求最小公倍数
    ans.s=(b.s*(gb/b.m)+a.s*(gb/a.m)),ans.m=gb;
    int ga=gcd(ans.s,ans.m);
    ans.s/=ga,ans.m/=ga;//这里再化简
    return ans;
}
void dfs(int x){
    if(t[x].size()==0){//是汇点
        res[x]=ad(res[x],a[x]);//res[x]代表汇点x的答案
        a[x].m=1,a[x].s=0;//此处清零避免重复加
        return;
    }
    fra tmp=a[x];
    tmp.m*=t[x].size();//此处将分母乘出边的个数相当于除以出边的个数
    for(int i=0;i<t[x].size();i++){
        a[t[x][i]]=ad(a[t[x][i]],tmp);//直接往下加
        dfs(t[x][i]);
    }
    a[x].cle();//此处清零避免重复加
}
signed main(){
    // freopen("water.in","r",stdin);
    // freopen("water.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++) res[i].cle();
    for(int i=1;i<=n;i++){//正常建图
        int x,y;
        x=read();
        for(int j=0;j<x;j++) y=read(),t[i].push_back(y);
    }
    for(int i=1;i<=m;i++){//对于每个源点都要跑一遍dfs，还要注意每个点的值要清零，源点设为1
        for(int j=1;j<=n;j++) a[j].cle();
        a[i].s=a[i].m=1;
        dfs(i);
    }
    for(int i=1;i<=n;i++){
        if(t[i].size()==0){//如果是汇点就输出
            print(res[i].s);
            printf(" ");
            print(res[i].m);
            printf("\n");
        }
    }
    return 0;
}

总结

是一道不算太难的题目，感觉出题人本意也不是要让写高精度，放在T1也不错，至少比CSP的良心了许多，对于萌新们也挺友好。难度感觉黄题差不多了。