求助,洛谷上有分,noip爆零
查看原帖
求助,洛谷上有分,noip爆零
357641
YyuanDa楼主2020/12/9 12:52
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int N=100005;
const int inf=0x3f3f3f3f;
typedef long long ll;
struct edge{
	int nxt,to;
}e[N<<1];
int head[N],rudu[N],chudu[N],cnt=0,n,m;

void add(int u,int v){
	e[++cnt].nxt=head[u];
	head[u]=cnt;
	e[cnt].to=v;
}

struct node{
	ll p,q;
}water[N];
queue<int> q;
vector<int> paishui;

ll gcd(ll a,ll b){
	if(b==0) return a;
	return gcd(b,a%b);
}
node mul(node z,int x){
	node res;
	if(x>0) {
		ll k=gcd(z.q,x);
		res.p=x*z.p/k,res.q=z.q/k;
	}else if(x<0){
		x=-x;
		ll k=gcd(z.p,x);
		res.p=z.p/k,res.q=z.q*x/k;
	}else return z;
	return res;
}
node pnd(node a,node b){
	if(a.p==0) return b;
	if(b.p==0) return a;
	node res;
	res.p=a.p*b.q+a.q*b.p,res.q=a.q*b.q;
	ll k=gcd(res.p,res.q);
	res.p/=k,res.q/=k;
	return res;
}
void init(){
	freopen("water.in","r",stdin);
	freopen("water.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		int d,tmp;
		scanf("%d",&d);
		chudu[i]=d;
		if(d==0) paishui.push_back(i);
		while(d--){
			scanf("%d",&tmp);
			add(i,tmp);
			rudu[tmp]++;
		}
	}
}

int main(){
	init();
	for(int i=1;i<=n;i++){
		if(rudu[i]==0){
			q.push(i);
			water[i].p=1ll,water[i].q=1ll;
		}
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		water[u]=mul(water[u],-chudu[u]);
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			rudu[v]--;
			water[v]=pnd(water[u],water[v]);
			if(chudu[v]==0) continue;
			if(rudu[v]==0) q.push(v);
		}
	}
	for(int i=0;i<paishui.size();i++)
		printf("%d %d\n",water[paishui[i]].p,water[paishui[i]].q);
	return 0;
}
2020/12/9 12:52
加载中...