求助大佬,被折磨一个晚上了
查看原帖
求助大佬,被折磨一个晚上了
261262
WaltVBAlston楼主2021/11/19 21:38

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

2021/11/19 21:38
加载中...