80分RE求条
查看原帖
80分RE求条
1028042
Jason_Harry_Song楼主2024/4/27 12:04
#include<bits/stdc++.h>
#define N 1100000
#define D 6
using namespace std;
int n,m,d[N],a[N][D];
int q[N],w[N],s[N],out[N];
bool hg[N];
struct Number{
	__int128 fz,fm;
	Number operator+(Number ot){
		__int128 gfm=fm/__gcd(fm,ot.fm)*ot.fm;
		__int128 fz1=gfm/fm*fz+gfm/ot.fm*ot.fz;
		__int128 gcd=__gcd(gfm,fz1);
		gfm/=gcd,fz1/=gcd;
		return{fz1,gfm};
	}
	Number operator*(Number ot){
		__int128 nfz=fz*ot.fz,nfm=fm*ot.fm;
		__int128 gcd=__gcd(nfz,nfm);
		nfz/=gcd,nfm/=gcd;
		return{nfz,nfm};
	}
}f[N];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&d[i]);
		for(int j=1;j<=d[i];j++)scanf("%d",&a[i][j]),s[a[i][j]]++;
	}
	set<pair<int,int>>st={};
	for(int i=1;i<=n;i++)st.insert({s[i],i});
	int cnt=0;
	while(st.empty()==false){
		if(st.begin()->first==0){
			cnt++,q[cnt]=st.begin()->second,w[q[cnt]]=cnt;
			for(int i=1;i<=d[q[cnt]];i++){
				st.erase({s[a[q[cnt]][i]],a[q[cnt]][i]});
				s[a[q[cnt]][i]]--;
				st.insert({s[a[q[cnt]][i]],a[q[cnt]][i]});
			}
			st.erase(st.begin());
		}else return 1;
	}
	for(int i=1;i<=m;i++)f[i]={1,1};
	for(int i=m+1;i<=n;i++)f[i]={0,1};
	for(int i=1;i<=n;i++)for(int j=1;j<=d[q[i]];j++)if(d[q[i]]!=0){
		f[w[a[q[i]][j]]]=f[w[a[q[i]][j]]]+Number({f[i].fz,f[i].fm*d[q[i]]});
	}
	for(int i=1;i<=n;i++)if(d[i]==0){
		__int128 x=f[w[i]].fz,y=f[w[i]].fm;
		int cnt=0;
		while(x>0)cnt++,out[cnt]=x%10,x/=10;
		if(cnt==0)printf("0 ");
		else{
			for(int i=cnt;i>=1;i--)printf("%d",out[i]);
			printf(" ");
		}
		cnt=0;
		while(y>0)cnt++,out[cnt]=y%10,y/=10;
		if(cnt==0)printf("0\n");
		else{
			for(int i=cnt;i>=1;i--)printf("%d",out[i]);
			printf("\n");
		}
	}
	return 0;
}

不理解拓扑排序中的 return 1 为何会被执行。

2024/4/27 12:04
加载中...