用了__int128,但还是不能过后四个点:
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>
#define ll __int128
using namespace std;
const int N = 1e5 + 10;
const int M = 5*N;
int gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a%b);}
int lcm(ll GCD, ll a, ll b) {return a /GCD * b;}
struct Frac {
ll a;
ll b;
void yuefen() {
ll GCD = gcd(a, b);
a /= GCD;
b /= GCD;
}
void tongfen(ll x) {
ll times = x / b;
b = x;
a *= times;
}
Frac operator / (ll x) {
Frac temp = *this;
temp.b *= x;
temp.yuefen();
return temp;
}
Frac operator + (const Frac& x) {
Frac t1 = *this;
Frac t2 = x;
ll LCM = lcm(gcd(t1.b, t2.b), t1.b, t2.b);
t1.tongfen(LCM); t2.tongfen(LCM);
t1.a = t1.a + t2.a;
t1.yuefen();
return t1;
}
Frac operator = (const Frac& x) {
this->a = x.a;
this->b = x.b;
}
};
ll read() {
ll s = 0, w = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') {s = s*10 + ch - '0'; ch = getchar();}
return s*w;
}
void write(ll n) {
if(n >= 10) write(n/10);
putchar(n%10 + '0');
}
int h[N], e[M], ne[M], idx; //链式前向星
int indeg[N]; //入度
int n, m;
vector<int> last; //最终结点
Frac water[N];
int d[N]; //出度
void init_G() {
memset(h, -1, sizeof(h));
memset(ne, -1, sizeof(ne));
idx = 0;
memset(indeg, 0, sizeof(indeg));
}
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void init_() {
init_G();
scanf("%d%d", &n, &m);
for(int i = 1; i<=n; i++) {
scanf("%d", &d[i]);
if(d[i] == 0) last.push_back(i);
for(int j = 0; j<d[i]; j++) {
int k; scanf("%d", &k);
add(i, k);
indeg[k]++;
}
}
for(int i = 1; i<=n; i++)
water[i] = {0, 0};
}
void solve() {
queue<int> q;
//找初始点
for(int i = 1; i<=n; i++) {
if(indeg[i] == 0 && !vis[i]) {
q.push(i);
water[i] = {1, 1};
}
}
while(!q.empty()) {
int t = q.front(); q.pop();
for(int p = h[t]; p != -1; p = ne[p]) {
int node = e[p];
if(water[node].a == 0 && water[node].b == 0) //分母为0特判
water[node] = water[t] / d[t];
else
water[node] = water[node] + (water[t] / d[t]);
if(--indeg[node] == 0) q.push(node);
}
}
for(int i : last) water[i].yuefen();
sort(last.begin(), last.end());
for(int i : last) {
write(water[i].a); putchar(' '); write(water[i].b); putchar('\n');
}
}
int main() {
init_();
solve();
return 0;
}