求助,为什么60分
查看原帖
求助,为什么60分
249683
CCCloud楼主2020/12/8 12:40
#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;

const int MAXN=1e5+5;
int n, m, h, t=1, cnt, qq[2*MAXN], a[MAXN], b[MAXN], v[MAXN][10];

struct Node
{
	ll p, q;
} d[MAXN];

inline int read()
{
	char ch=getchar();
	int f=1, x=0;
	while(ch<'0' || ch>'9') if(ch=='-') f=-1, ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+(ch^48), ch=getchar();
	return f*x;
}

int g(ll a, ll b)
{
	if(b==0) return a;
	return g(b, a%b);
}

int l(ll a, ll b)
{
	return a*b/g(a, b);
}

void jia(ll p, ll q, int num)
{
	//printf("%d %d %d\n", p, q, num);
	ll p1=d[num].p, q1=d[num].q;
	if(p1==0 && q1==0)
	{
		d[num].p=p, d[num].q=q;
		return;
	}
	ll q2=l(q, q1);
	p1=p*(q2/q)+p1*(q2/q1);
	d[num].p=p1, d[num].q=q2;
}

void yue(int i)
{
	ll x=g(d[i].p, d[i].q);
	d[i].p/=x, d[i].q/=x;
}

int main(void)
{
	//freopen("water.in", "r", stdin);
	//freopen("water.out", "w", stdout);
	n=read(), m=read();
	for(int i=1; i<=n; i++)
	{
		a[i]=read();//chu du
		for(int j=1; j<=a[i]; j++)
		{
			int x;
			x=read();
			v[i][j-1]=x;
			b[x]++;//ru du
		}
	}
	for(int i=1; i<=m; i++)
		d[i].p=1, d[i].q=1;
	for(int i=1; i<=n; i++)
		if(!b[i]) qq[++h]=i;

	while(t<=h)
	{
		//printf("%d\n", q.front());
		int x=qq[t++];
		for(int i=0; i<a[x]; i++)
		{
			int y=v[x][i];
			//printf("%d\n", y);
			jia(d[x].p, d[x].q*a[x], y);
			b[y]--;
			if(!b[y]) qq[++h]=y;
		}
		//puts("");
	}
	for(int i=1; i<=n; i++)
		if(!a[i]) yue(i), printf("%llu %llu\n", d[i].p, d[i].q);
	
	return 0;
}
2020/12/8 12:40
加载中...