【正经题解】排水系统

直接对于每个源点跑dfs统计答案

#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;
}