原题链接题意分析城市的排水系统是一个n个节点的DAG(有向无环)图有m个污水接收口且每个污水接收口有1吨的水放水过程中会平均分给子节点没有子节点的水管就是最终排水口,最后按编号顺序输出每个最终排水点的污水(以分数形式)。思路考虑到图是稀疏图(0 ≤ d i ≤ 5 0 \le d_i \le 50≤di​≤5)以邻接表存图然后以拓扑排序模拟污水流动模拟过程中我们以一个n大小的数组存当前每一个顶点所对应的污水量(以分数形式存储)污水流动的计算其实就是两个分数相加先算分母a与c的最小公倍数gbsa*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/ad*gbs/c}{gbs}ab​cd​gbsb∗gbs/ad∗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}1024,310220,410220,510230,故分子必然小于2 74 2^{74}274,我们使用c11标准中提供的_int128必然可解决这个问题,即可拿到100分.此处请注意:__int128不能用cout或printf输出故需要自己实现输出AC代码(因使用了__int128请以c11及以上标准提交)#includebits/stdc.husing namespace std;typedef__int128 lll;constintMAXN1e55;vectorintedge[MAXN];// 邻接表intrd[MAXN];// 入度数组lll wus[MAXN][2];// 当前污水量lllgcd(lll a,lll b){if(b0)returna;returngcd(b,a%b);}// 打印__int128类型变量voidwrite(lll num){if(num0){putchar(-);num-num;}if(num9)write(num/10);putchar(num%100);}intmain(){intn,m;cinnm;// 邻接表存图并处理入度数组intd,c;memset(rd,0,sizeof(rd));for(inti1;in;i){edge[i].clear();cind;for(intj1;jd;j){cinc;rd[c];edge[i].push_back(c);}}// 拓扑排序for(inti1;in;i)wus[i][0]0,wus[i][1]1;//最开始每个位置的污水都是0/1,即为0.queueintque;for(inti1;im;i){que.push(i);wus[i][0]1;}while(!que.empty()){inttopque.front();que.pop();inttempedge[top].size();if(temp){wus[top][1]*temp;//top的污水量先除temp方便下面运算// top向所有子节点排污水for(inti0;itemp;i){// top-edge[top][i] 排污水// top的污水排向edge[top][i]的计算实则两个分数的求和,参考思路中的公式lll gbswus[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(inti1;in;i){if(wus[i][0]){lll kkgcd(wus[i][0],wus[i][1]);write(wus[i][0]/kk);cout ;write(wus[i][1]/kk);coutendl;}}return0;}