拓扑排序+__int128做的,60pts,求调
查看原帖
拓扑排序+__int128做的,60pts,求调
641153
changbijie_1019楼主2023/11/11 13:58
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+9;
using namespace std;
int n,m,in[N],out[N];
struct fraction{
	__int128 fz,fm;
}f[N];
void handle(int k){
	int gcd=__gcd(f[k].fz,f[k].fm);
	f[k].fz/=gcd; f[k].fm/=gcd;
} 
vector<int> d[N];
void add(int u,int v){
	d[u].push_back(v);
}
void addnum(int a,int b){
	if(f[a].fz==0&&f[a].fm==0){
		f[a].fz=f[b].fz;
		f[a].fm=f[b].fm;
		return;
	}
	int fz=f[a].fz*f[b].fm+f[a].fm*f[b].fz;
	int fm=f[a].fm*f[b].fm;
	int gcd=__gcd(fz,fm);
	f[a].fz=fz/gcd; f[a].fm=fm/gcd; 
}
void print(__int128 x){
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>out[i];
		for(int j=1;j<=out[i];j++){
			int u; cin>>u;
			add(i,u);
			in[u]++;
		}
	}
	for(int i=1;i<=m;i++) f[i].fz=f[i].fm=1;
	queue<int> q;
	for(int i=1;i<=n;i++){
		if(in[i]==0) q.push(i);
		else continue;
	}
	while(q.empty()==false){
		int u=q.front(); q.pop();
		if(out[u]==0) continue;
		f[n+1]=(fraction){f[u].fz,f[u].fm};//f[n+1]为temp 
		f[n+1].fm*=out[u];
		//temp代表u流到自己邻居的量为多少 
		handle(n+1);
		for(int i=0;i<d[u].size();i++){
			int v=d[u][i];
			in[v]--;
			if(in[v]==0) q.push(v);
			addnum(v,n+1);
		}
	}
	for(int i=1;i<=n;i++){
		if(out[i]==0){
//			cout<<f[i].fz<<" "<<f[i].fm<<endl;
			print(f[i].fz);
			cout<<" ";
			print(f[i].fm);
			cout<<endl;
		}
		else continue;
	}
	return 0;
}
2023/11/11 13:58
加载中...