P7113 [NOIP2020] 排水系统 （拓扑排序）

（不想打高精，也不想学习其他大佬的神仙写法，打了90分的错解）。

本题容易想到用拓扑排序处理，涉及分数的加法，用long long会超时，不过通分时先除后乘卡一下也可以拿90分。

结构体真是个复杂的东西，代码11行是无参数的构造函数，似乎是初始化的，分子为0，分母为1。

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define ll long long

 4 #define N 100005

 5 ll gcd(ll a,ll b){

 6     if(!b) return a;

 7     return gcd(b,a%b);

 8 }

 9 struct FS{

10     ll fz,fm;

11     FS(){fz=0,fm=1;}

12     void chu(int x){//先除后乘

13         int g=gcd(x,fz);

14         fz/=g;

15         x/=g;

16         fm*=x;

17     }

18 }v[N];

19

20 FS add(FS A,FS B){

21     ll nfm=A.fm/gcd(A.fm,B.fm)*B.fm;//通分

22     A.fz*=nfm/A.fm;

23     B.fz*=nfm/B.fm;

24     A.fz+=B.fz;

25     A.fm=nfm;

26     nfm=gcd(A.fz,A.fm);

27     A.fz/=nfm;

28     A.fm/=nfm;

29     return A;

30 }

31

32 struct node{

33     int to,nxt;

34 }e[N*5];

35 int n,m,tot,head[N],rd[N],cd[N];

36 queue<int> q;

37 void build(int a,int b){

38     ++rd[b];

39     e[++tot].to=b;

40     e[tot].nxt=head[a];

41     head[a]=tot;

42 }

43

44 int main(){

45     scanf("%d%d",&n,&m);

46     for(int to,i=1;i<=n;i++){

47         scanf("%d",&cd[i]);

48         for(int j=1;j<=cd[i];j++){

49             scanf("%d",&to);

50             build(i,to);

51         }

52     }

53     for(int i=1;i<=m;i++)

54         v[i].fz=v[i].fm=1;

55     int p;

56     for(int i=1;i<=n;i++){

57         if(!rd[i]) q.push(i);

58     }

59     while(!q.empty()){

60         p=q.front();q.pop();

61         if(cd[p]) v[p].chu(cd[p]);//均分

62         for(int i=head[p];i;i=e[i].nxt){

63             --rd[e[i].to];

64             if(!rd[e[i].to]) q.push(e[i].to);

65             v[e[i].to]=add(v[e[i].to],v[p]);

66         }

67     }

68     for(int i=1;i<=n;i++)

69         if(!cd[i]) printf("%lld %lld\n",v[i].fz,v[i].fm);

70     return 0;

71 }

P7113 [NOIP2020] 排水系统 （拓扑排序）的相关教程结束。