学了一下__int128做道水题练练手
topsort
进行拓扑排序即可
如果不用高精度,可以用__int128
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
vector<int> G[N];
int n,m;
struct Num{
__int128 a,b;
}v[N];
__int128 gcd(__int128 a,__int128 b){
return b>0?gcd(b,a%b):a;
}
void write(__int128 x){
if(x<10)putchar('0' + x);
else{
write(x/10);
write(x%10);
}
}
Num add(Num A,Num B){
__int128 a = A.a,b = A.b,c = B.a,d = B.b;
__int128 e = b*d;
__int128 f = a*d+b*c;
__int128 gg = gcd(e,f);
e = e/gg,f = f/gg;
Num res;res.a = f,res.b = e;
return res;
}
int rd[N],cd[N];
void topsort(){
queue<int> q;
for(int i = 1;i<=n;i++){
if(!rd[i])q.push(i);
}
while(q.size()){
int t = q.front();q.pop();
if(cd[t])v[t].b = v[t].b * (__int128)cd[t];
for(auto i:G[t]){
rd[i] --;
v[i] = add(v[i],v[t]);
if(!rd[i])q.push(i);
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++){
if(i<=m)v[i].a = 1;
v[i].b = 1;
scanf("%d",&cd[i]);
for(int j = 1;j<=cd[i];j++){
int b;scanf("%d",&b);
G[i].push_back(b);
rd[b] ++;
}
}
topsort();
for(int i = 1;i<=n;i++){
if(cd[i] == 0){
write(v[i].a);
printf(" ");
write(v[i].b);
printf("\n");
}
}
return 0;
}