20pts求助
查看原帖
20pts求助
730717
wanwang楼主2023/7/23 14:05
#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
int n,m,wp[MAXN],wq[MAXN],e[MAXN],ans=0,d[MAXN];
bool edge[1001][1001];
void with(int x,int y){
	if(wq[x]==wq[y]){
		wp[y]+=wp[x];
		int gcd=__gcd(wp[y],wq[y]);
		wp[y]/=gcd;
		wq[y]/=gcd;
	}
	else{
		int xp=wp[x],xq=wq[x];
		wp[y]=xp*wq[y]+xq*wp[y];
		wq[y]*=xq;
		int gcd=__gcd(wp[y],wq[y]);
		wp[y]/=gcd;
		wq[y]/=gcd;
	}
}
void bfs(){
	for(int i=1;i<=n-ans;i++){
		if(i<=m)wp[i]=1;
		wq[i]*=d[i];
		for(int j=1;j<=n;j++)
			if(edge[i][j])with(i,j);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		wq[i]=1;
		int a[10];
		cin>>d[i];
		for(int j=1;j<=d[i];j++){
			cin>>a[j];
			edge[i][a[j]]=1;
		}
		if(d[i]==0)e[++ans]=i;
	}
	bfs();
	for(int i=1;i<=ans;i++)
		cout<<wp[e[i]]<<" "<<wq[e[i]]<<"\n";
	return 0;
}
2023/7/23 14:05
加载中...