30分RE求助
查看原帖
30分RE求助
175533
Gianthard_陈昱衡楼主2021/11/17 23:58
#include<bits/stdc++.h>
typedef unsigned long long ull;
int n,m;

#define MAXN 200010



namespace GH{
	
	class fs{
		public:
			int p,q;
			fs(ull p = 0,ull q = 1):p(p),q(q){}
			fs operator + (fs b){
				fs res(p*b.q+q*b.p,q*b.q);
				ull g = std::__gcd(res.p,res.q);
				res.p/=g;
				res.q/=g;
				return res;
			}
			fs operator / (int b){
				fs res(p,q*b);
//				res.print();
//				std::cout<<'\n';
				ull g = ull(std::__gcd(res.p,res.q));
				res.p/=g;
				res.q/=g;
				return res;
			}
			void print(){
				std::cout<<p<<'/'<<q<<std::endl;
			}
	};
	
	class node{
		public:
			int in;
			std::vector<int> out;
			fs value;
	}Nodes[MAXN];
}



bool cmp(GH::node a,GH::node b){
	return a.in<b.in;
}

void flood(int n,GH::fs v){
//	std::cout<<"v:";
//	v.print();
//	std::cout<<'\n'; 
	for(unsigned int i = 0;i < GH::Nodes[n].out.size();i++){
//		std::cout<<'\n';
//		GH::Nodes[GH::Nodes[n].out[i]].value.print();
		GH::Nodes[GH::Nodes[n].out[i]].value = v/GH::Nodes[n].out.size() + GH::Nodes[GH::Nodes[n].out[i]].value;
		GH::Nodes[n].value = GH::fs(0,1);
//		GH::Nodes[GH::Nodes[n].out[i]].value.print();
	}
}

void tpsort(){
	std::queue<int> q;
	for(int i = 1;i <= n;i++){
		if(GH::Nodes[i].in == 0){
			q.push(i);
		}
	}
	
	while(!q.empty()){
//		std::cout<<q.size()<<'\n';
		int x = q.front();
//		std::cout<<x<<'\n';
		q.pop();
		for(unsigned int i = 0;i < GH::Nodes[x].out.size();i++){
//			std::cout<<x<<'\n';
			GH::Nodes[GH::Nodes[x].out[i]].in -= 1;
//			GH::Nodes[x].value.print();
//			std::cout<<std::endl;
			flood(x,GH::Nodes[x].value);
			if(GH::Nodes[GH::Nodes[x].out[i]].in == 0)
  				q.push(GH::Nodes[x].out[i]);
		}
	}
}
int main(){
	std::cin>>n>>m;
	for(int i = 1;i <= n;i++){
		int d = 0;
		std::cin>>d;
		while(d){
			d--;
			int tmp;
			std::cin>>tmp;
			GH::Nodes[i].out.push_back(tmp);
			GH::Nodes[tmp].in++; 
		}
	}
	
	for(int i = 1;i <= n;i++){
		if(!GH::Nodes[i].in)
			GH::Nodes[i].value = GH::fs(1,1);
	}
	
	tpsort();
	
	for(int i = 1;i <= n;i++){
		if(!GH::Nodes[i].out.size())
  		std::cout<<GH::Nodes[i].value.p<<' '<<GH::Nodes[i].value.q<<'\n';
	}
//	GH::fs test = GH::fs(2,3);
//	std::cout<<(test/6).p<<'/'<<(test/6).q<<std::endl;
	return 0;
}

RT,只有前三个点AC

2021/11/17 23:58
加载中...