求助
查看原帖
求助
67943
Jelly5233楼主2020/12/7 17:29

为什么re了啊,求大佬看看…

#include<bits/stdc++.h>
using  namespace std;
struct frozen{
	int to,next;
}c[100005];
long long cnt=0,head[100005],p[100005]={0},q[100005]={0},num[100005],rd[100005]={0},n,m;
void add(int x,int y){
	cnt++;
	c[cnt].to=y;
	c[cnt].next=head[x];
	head[x]=cnt;
}
int gcdd(int x,int y){
	if(y==0)return x;
	else return gcdd(y,x%y);
}
void jia(int x,int y)
{
	
	int md=gcdd(q[x]*num[x],q[y]);
	if(p[y]==0&&q[y]==0)
	{
		p[y]=p[x];
		q[y]=num[x]*q[x]; 
	} 
	else if(q[x]*num[x]==q[y])p[y]+=p[x];
	else {
		p[y]=p[x]*((num[x]*q[x]*q[y])/md/(q[x]*num[x]))+(p[y]*(num[x]*q[x]*q[y])/md/q[y]);
		q[y]=(num[x]*q[x]*q[y])/md;
	}
	md=gcdd(q[y],p[y]);
	q[y]=q[y]/md;
	p[y]=p[y]/md;
}
int main(){	
//	freopen("water.in","r",stdin);
//	freopen("water.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	queue<int> qu;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&num[i]);
		for(int j=1;j<=num[i];j++)
		 {
		 	int x;
		 	scanf("%lld",&x);
		 	rd[x]++;
		 	add(i,x);
		 }
	}
	for(int i=1;i<=n;i++)
	if(rd[i]==0){
		qu.push(i);		
		p[i]=1;
		q[i]=1;
	}
	while(!qu.empty()){
		int s=qu.front();
		qu.pop();
		if(num[s]!=0)
		{
		for(int i=head[s];i;i=c[i].next)
		{
			rd[c[i].to]--;
			jia(s,c[i].to);
			if(rd[c[i].to]==0)qu.push(c[i].to);
		}
		q[s]=p[s]=0;
	}
	} 
	for(int i=1;i<=n;i++)
	if(q[i]!=0)printf("%lld %lld\n",p[i],q[i]);
//	fclose(stdin);
//	fclose(stdout);
	return 0; 
}
2020/12/7 17:29
加载中...