T1 30 AFO
  • 板块灌水区
  • 楼主phigy
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/12/5 22:36
  • 上次更新2023/11/5 06:34:28
查看原帖
T1 30 AFO
115359
phigy楼主2020/12/5 22:36

求大佬看看哪里写错了

#include <iostream>
#include <queue>
#include <cstdio>


using namespace std;

long long n,m;
long long a[1000000];
struct edge
{
	long long next,to;
}e[1000005];
struct Q
{
	long long p,q;
}w[1000005];

long long cnt,head[1000005];
void add(long long x,long long y)
{
	cnt++;
	e[cnt].next=head[x];
	e[cnt].to=y;
	head[x]=cnt;
}

long long book[1000005];
long long b[1000005];
long long num[1000005];

long long gcd(long long a,long long b)
{
	if(a<b)swap(a,b);
	if(b==0)return a;
	if(a==0)return b;
	return gcd(b,a%b);
}

int main()
{
	//freopen("water.in","r",stdin);
	//freopen("water.out","w",stdout);
	long long i,j,k;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		long long x;
		cin>>num[i];
		for(j=1;j<=num[i];j++)
		{
			long long y;
			cin>>y;
			add(i,y);
		}
		if(num[i]==0)
		{
			book[i]=1;
		}
	}
	queue<long long>q;
	for(i=1;i<=m;i++)
	{
		q.push(i);
		w[i].p=1;
		w[i].q=1;
		b[i]=1;
	}
	while(!q.empty())
	{
		long long u=q.front();
		//cout<<u<<endl;
		q.pop();
		b[u]=0;
		if(!book[u])
		w[u].q*=num[u];
		for(i=head[u];i;i=e[i].next)
		{
			long long v=e[i].to;
			if(w[v].p==0)
			{
				w[v].p=w[u].p;
				w[v].q=w[u].q;
			}
			else
			{
				//cout<<w[u].p<<' '<<w[u].q<<endl<<w[v].p<<' '<<w[v].q<<endl;
				w[v].p=w[u].p*w[v].q+w[u].q*w[v].p;
				w[v].q=w[u].q*w[v].q;
				long long gc=gcd(w[v].p,w[v].q);
				w[v].p/=gc;
				w[v].q/=gc;
				//cout<<w[v].p<<' '<<w[v].q<<endl<<endl;
			}
			if(b[v]==0)
			{
				b[v]=1;
				q.push(v);
			}
		}
		if(!book[u])
		{
			w[u].p=0;
			w[u].q=0;
		}
	}
	for(i=1;i<=n;i++)
	{
		if(book[i]==1)
		{
			cout<<w[i].p<<' '<<w[i].q<<endl;
		}
	}
	return 0;
}
/*
5 1
3 2 3 5
2 4 5
2 5 4
0
0
*/
2020/12/5 22:36
加载中...