long double求调
查看原帖
long double求调
398687
allenyuan9038074楼主2023/11/16 19:59
#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define int long long
#define eps 1e-20
vector<int> g[N];
int rd[N];
long double w[N][2];
int q[N],n;
long double gcd(long double x,long double y){
	if(x==0 || y==0) return 1;
    long double r=x-floorl(x/y)*y;
    while(fabsl(r)>eps){
        x=y;
        y=r;
        r=x-floorl(x/y)*y;
    }
    return y;
}
void upd(int u){
	long double x=gcd(w[u][1],w[u][0]);
	w[u][1]/=x;
	w[u][0]/=x;
}
void topo(){
	int l=1,r=0;
	for(int i=1;i<=n;i++){
		if(rd[i]==0){
			q[++r]=i;
			w[i][0]=1;
			w[i][1]=1;
		}
	}
	while(l<=r){
		int u=q[l];
		if(g[u].size()) w[u][0]*=(long double)g[u].size();
		upd(u);
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i];
			if(w[v][1]==0 || w[v][0]==0){
				w[v][1]=w[u][1];
				w[v][0]=w[u][0];
			}
			else{
				w[v][1]=w[u][1]*w[v][0]+w[v][1]*w[u][0];
				w[v][0]=w[u][0]*w[v][0];
			}
			upd(v);
			rd[v]--;
			if(rd[v]==0) q[++r]=v;
		}
		if(g[u].size()) w[u][1]=w[u][0]=0;
		l++;
	}
}
signed main(){
	int m,x,y;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>x;
		for(int j=1;j<=x;j++){
			cin>>y;
			g[i].push_back(y);
			rd[y]++;
		}
	}
	topo();
	for(int i=1;i<=n;i++){
		upd(i);
		if(w[i][1]!=0 && w[i][0]!=0) cout<<fixed<<setprecision(0)<<w[i][1]<<" "<<w[i][0]<<endl;
	}
	return 0;
}
2023/11/16 19:59
加载中...