已开__int128,仍WA最后一个测试点,代码如下
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100009;
int n,m;
vector<vector<int>> adj(n+1);
void print(__int128 x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) print(x / 10);
putchar(x % 10 + '0');
}
struct Fraction{
__int128 p,q;
Fraction(int _p=0,int _q=1){
int g=gcd(abs(_p),abs(_q));
p=_p/g;
q=_q/g;
if(q<0)p=-p,q=-q;
if(p==0)q=1;
}
static int gcd(int a,int b) {
while(b){
int t=b;
b=a%b;
a=t;
}
return a;
}
static int lcm(int a,int b) {
return a/gcd(a,b)*b;
}
Fraction operator+(const Fraction&o)const{
int l=lcm(q,o.q);
return {p*(l/q)+o.p*(l/o.q),l};
}
Fraction operator/(int d)const{
return {p,q*d};
}
};
signed main() {
cin>>n>>m;
vector<int>in_degree(n+1,0);
vector<int>out_degree(n+1,0);
vector<vector<int> >adj(n+1);
for(int i=1,d;i<=n;i++){
cin>>d;
out_degree[i]=d;
for(int j=0,a;j<d;j++){
cin>>a;
adj[i].push_back(a);
in_degree[a]++;
}
}
vector<Fraction> water(n+1,Fraction(0,1));
queue<int> q;
for(int i=1;i<=m;i++){
water[i]=Fraction(1,1);
q.push(i);
}
while(!q.empty()){
int u=q.front();
q.pop();
if(out_degree[u]==0)continue;
Fraction divided=water[u]/out_degree[u];
water[u]=Fraction(0,1);
for(int j=0;j<adj[u].size();j++){
int v=adj[u][j];
water[v]=water[v]+divided;
in_degree[v]--;
if(in_degree[v]==0){
q.push(v);
}
}
}
for(int i=1;i<=n;i++){
if(out_degree[i]==0&&water[i].p!=0){
print(water[i].p);
cout<<" ";
print(water[i].q);
cout<<endl;
}
}
return 0;
}
AC互关