65016 - [NOIP2020] 排水系统 water

题目大意

给定n个结点和di个单向管道，从接收口出发，排水口结束，每次经过结点将污水均分。

解题思路 在输入的时候先确定没有管道通向自身的是接收口，可以用数组标记求解。判断自身通向其他地方的管子数是0来确定是不是排水口。

采用bfs拓扑排序的思路，先用队列把接收口读入，用bfs进行搜索，过程的时候注意如果前面还有管道要到达自身，就先不读入队列，当上面的水全部到达这一层时在入队，可以在输入时用数组计数判断自身到达的次数，最后是水的求和部分，直接2个分数加起来 ，然后找最大公约数进行约分。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int> q[N];
int A[N], B[N], tot1, tot2;
__int128 ans1[N], ans2[N];
__int128 gcd(__int128 a, __int128 b) {
	return (b == 0 ? a : gcd(b, a % b));
}
void dfs(int u) {
	int cnt = q[u].size();
	__int128 x = ans1[u], y = ans2[u];
	for (int i = 0; i < q[u].size(); ++i) {
		int v = q[u][i]; 
		__int128 cnt1 = ans1[v], cnt2 = ans2[v], cnt3 = x, cnt4 = y * cnt, tmp = cnt2 * cnt4 / gcd(cnt2, cnt4);
		cnt1 *= tmp / cnt2; cnt3 *= tmp / cnt4; cnt1 += cnt3; cnt2 = tmp;
		__int128 G = gcd(cnt1, cnt2);
		cnt1 /= G; cnt2 /= G; ans1[v] = cnt1; ans2[v] = cnt2; ans1[u] = 0; ans2[u] = 1;
		dfs(v);
	}
	return;
}
void print(__int128 n) {
    if (n > 9) {
		print(n / 10);
	}
    putchar(n % 10 + 48);
}
int main() {
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		int x; cin >> x;
		if (!x) {
			B[++tot2] = i;
		}
		for (int j = 1; j <= x; ++j) {
			int y; cin >> y;
			q[i].push_back(y); ++A[y];
		}
	}
	for (int i = 1; i <= n; ++i) { 
		ans2[i] = 1;
	} 
	for (int i = 1; i <= n; ++i) { 
		if (!A[i]) {
			ans1[i] = 1;
			dfs(i);
		}
	}
	for (int i = 1; i <= tot2; ++i) {
		print(ans1[B[i]]); cout << ' '; print(ans2[B[i]]); cout << '\n';
	}
	return 0;
}