RT,被一道简单拓扑弄了一晚上,真的撑不下去了,求大佬帮忙看看,谢谢!!!
code:
#include<iostream>
#include<queue>
#include<cstdio>
#define int unsigned long long
using namespace std;
int fenmu[100005],fenzi[100005],before[1000005],now[100005],u[1000005],v[1000005];
int n,m,e=0;
int rudu[100005],chudu[100005];
int paichu=0,pai[100005];
queue <int> q;
inline int read(){
int x=0;
char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x;
}
void print(int x){
int k=0;
char num[10005];
while(x){
num[++k]=x%10+'0';
x/=10;
}
while(k)
putchar(num[k--]);
putchar('\n');
return;
}
void tuopu(){
while(!q.empty()){
int x=q.front();
q.pop();
if(chudu[x]==0)
continue;
fenmu[x]*=chudu[x];
//cout<<x<<" "<<fenmu[x]<<" "<<fenzi[x]<<" "<<chudu[x]<<endl;
for(int i=now[x];i!=-1;i=before[i]){
fenzi[v[i]]=fenzi[v[i]]*fenmu[x]+fenmu[v[i]]*fenzi[x];
//cout<<114514<<" "<<fenmu[v[i]]<<" "<<temp_fenzi<<endl;
//cout<<fenmu[v[i]]<<endl;
fenmu[v[i]]*=fenmu[x];
rudu[v[i]]--;
if(!rudu[v[i]])
q.push(v[i]);
}
}
return;
}
int gcd(int x,int y){
while(y!=0){
int t=x%y;
x=y,y=t;
}
return x;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
now[i]=-1;
fenzi[i]=0;
fenmu[i]=1;
if(i<=m)
fenzi[i]=1;
rudu[i]=0;
}
for(int i=1;i<=n;i++){
int x;
cin>>x;
if(x==0)
pai[++paichu]=i;
chudu[i]=x;
while(x--){
e++;
u[e]=i;
cin>>v[e];
before[e]=now[u[e]];
now[u[e]]=e;
rudu[v[e]]++;
}
}
for(int i=1;i<=n;i++)
if(rudu[i]==0)
q.push(i);
tuopu();
for(int i=1;i<=paichu;i++){
while(gcd(fenzi[pai[i]],fenmu[pai[i]])!=1){
int t=gcd(fenzi[pai[i]],fenmu[pai[i]]);
fenzi[pai[i]]/=t;
fenmu[pai[i]]/=t;
}
cout<<fenzi[pai[i]]<<" "<<fenmu[pai[i]]<<endl;
}
return 0;
}
理论上来说是能拿60的,但是大样例死循环,#4结果错误洛谷显示re