OItiku 90 求助
查看原帖
OItiku 90 求助
261417
asasas楼主2020/12/5 19:04

RT

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define ll long long
vector <int> edge[100005];
struct as{
	ll a,b;
}a[100005];
bool vis[100005],asas[100005];
int in[100005],out[100005];
inline ll gcd(ll a,ll b){
	if (b==0) return a;
	return 	gcd(b,a%b);
}
ll lcm(ll a,ll b){
	return a*b/gcd(a,b);
	}
as add(as a,as b){
	as c;
	int qwq=lcm(a.b,b.b);
	a.a=a.a*qwq/a.b,b.a=b.a*qwq/b.b;
	a.b=qwq,b.b=qwq;
	c.b=qwq;
	c.a=a.a+b.a;
	int pwq=gcd(c.a,c.b);
	c.a/=pwq,c.b/=pwq;
	return c;
	}
as divd(as a,ll b){
	as c;
	int qwq=gcd(a.a,b);
	c.a=a.a/qwq;
	c.b=a.b*b/qwq;
	return c;
	}
void dfs(int fa,int now,as aq){
	int qwq=edge[now].size();
	a[now]=add(a[now],aq);
	as zyq=divd(a[now],qwq);
	if (asas[now]==0) a[now].a=0;
	for (register int i=0;i<qwq;i++){
			int p=edge[now][i]; 
			if (fa==now){
				continue ;
				} 
			dfs(now,p,zyq);
		}
	}	
int main(){
	freopen("water.in","r",stdin);
	freopen("water.out","w",stdout);
	int n,m,len=0;
	scanf("%d %d",&n,&m);
	for (register int i=1;i<=n;i++){
		int t;
		scanf("%d",&t);
		if (t==0) {
			out[++len]=i;
			asas[i]=1;
			a[i].b=1;
			continue ;
			}
		while(t--){
			int qwq;
			scanf("%d",&qwq);
			edge[i].push_back(qwq);
			}
			a[i].b=1;
		}
		for (register int i=1;i<=m;i++){
			a[i].a=1;
			}
			for (register int i=1;i<=m;i++){
				as c;
				c.a=0,c.b=1; 
				 vis[i]=1;
				 dfs(0,i,c);
				}
				for (register int i=1;i<=len;i++){
			    printf("%lld %lld\n",a[out[i]].a,a[out[i]].b/*a[i].a,a[i].b*/);
			}
	return 0;
}
2020/12/5 19:04
加载中...