题解)
原题链接
题意分析：
城市的排水系统是一个n个节点的DAG(有向无环)图，有m个污水接收口且每个污水接收口有1吨的水，放水过程中会平均分给子节点，没有子节点的水管就是最终排水口,最后按编号顺序输出每个最终排水点的污水(以分数形式)。
思路：
考虑到图是稀疏图(0 ≤ d i ≤ 5 0 \le d_i \le 50≤di≤5)，以邻接表存图，然后以拓扑排序模拟污水流动，模拟过程中我们以一个n大小的数组，存当前每一个顶点所对应的污水量(以分数形式存储)，污水流动的计算其实就是两个分数相加，先算分母a与c的最小公倍数gbs=a*c/gcd(a,c),再根据以下公式将分数相加:
b a + d c = b ∗ g b s / a + d ∗ g b s / c g b s \frac{b}{a} + \frac{d}{c}=\frac{b*gbs/a+d*gbs/c}{gbs}ab+cd=gbsb∗gbs/a+d∗gbs/c
然而这道题的分母,根据题意(水在从一个接收口流向一个最终排水口的过程中，不会经过超过 10 个中间排水结点),故而分母在计算过程中最坏情况下会达到3 10 ∗ 4 10 ∗ 5 10 3^{10}*4^{10}*5^{10}310∗410∗510,且最多放10吨水,故而分子最大可达到分母的10倍:10 ∗ 3 10 ∗ 4 10 ∗ 5 10 10*3^{10}*4^{10}*5^{10}10∗310∗410∗510,这会爆掉int(只能拿30分)，long long也会爆(只能拿60分),所以需要更高精度的手段处理分母.
这里有两种解决方案.第一种是采用高精度算法,然而观察上述分数相加的公式,我们需要实现大数加乘除求余才能解决这个问题,太过麻烦.
考虑10 ∗ 3 10 ∗ 4 10 ∗ 5 10 10*3^{10}*4^{10}*5^{10}10∗310∗410∗510中10 < 2 4 , 3 10 < 2 20 , 4 10 = 2 20 , 5 10 < 2 30 10< 2^{4},3^{10}< 2^{20},4^{10}= 2^{20},5^{10}<2^{30}10<24,310<220,410=220,510<230,故分子必然小于2 74 2^{74}274,我们使用c++11标准中提供的_int128必然可解决这个问题,即可拿到100分.
此处请注意:__int128不能用cout或printf输出故需要自己实现输出
AC代码(因使用了__int128请以c++11及以上标准提交)
#include<bits/stdc++.h>using namespace std;typedef__int128 lll;constintMAXN=1e5+5;vector<int>edge[MAXN];// 邻接表intrd[MAXN];// 入度数组lll wus[MAXN][2];// 当前污水量lllgcd(lll a,lll b){if(b==0)returna;returngcd(b,a%b);}// 打印__int128类型变量voidwrite(lll num){if(num<0){putchar('-');num=-num;}if(num>9)write(num/10);putchar(num%10+'0');}intmain(){intn,m;cin>>n>>m;// 邻接表存图并处理入度数组intd,c;memset(rd,0,sizeof(rd));for(inti=1;i<=n;i++){edge[i].clear();cin>>d;for(intj=1;j<=d;j++){cin>>c;rd[c]++;edge[i].push_back(c);}}// 拓扑排序for(inti=1;i<=n;i++)wus[i][0]=0,wus[i][1]=1;//最开始每个位置的污水都是0/1,即为0.queue<int>que;for(inti=1;i<=m;i++){que.push(i);wus[i][0]=1;}while(!que.empty()){inttop=que.front();que.pop();inttemp=edge[top].size();if(temp){wus[top][1]*=temp;//top的污水量先除temp方便下面运算// top向所有子节点排污水for(inti=0;i<temp;i++){// top->edge[top][i] 排污水// top的污水排向edge[top][i]的计算实则两个分数的求和,参考思路中的公式lll gbs=wus[top][1]*wus[edge[top][i]][1]/gcd(wus[top][1],wus[edge[top][i]][1]);wus[edge[top][i]][0]=wus[top][0]*(gbs/wus[top][1])+wus[edge[top][i]][0]*(gbs/wus[edge[top][i]][1]);wus[edge[top][i]][1]=gbs;if(--rd[edge[top][i]]==0)que.push(edge[top][i]);}// 排完污水后,top位置污水清0wus[top][0]=0;wus[top][1]=1;}}// 按编号顺序输出每个点的污水量for(inti=1;i<=n;i++){if(wus[i][0]){lll kk=gcd(wus[i][0],wus[i][1]);write(wus[i][0]/kk);cout<<" ";write(wus[i][1]/kk);cout<<endl;}}return0;}
