P7113 [NOIP2020] 排水系统 60pts(wa) 求助
查看原帖
P7113 [NOIP2020] 排水系统 60pts(wa) 求助
112048
dfydn楼主2021/8/17 15:38
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int N=100005;
ll sum1[N],sum2[N];
int tot,n,m;
ll in[N],out[N]; 
int head[N];
ll read(){
	int num=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c<='9'&&c>='0'){
		num=num*10+c-'0';
		c=getchar();
	}
	return num*f;
}
queue<int> q;
struct node{
	int to,next;
}edge[N<<1];
void add(int u,int v){
	edge[tot].to=v;
	edge[tot].next=head[u];
	head[u]=tot++;
}
ll gcd(ll x,ll y){
	if(y==0) return x;
	return gcd(y,x%y);
}
void toposort(){
	for(int i=1;i<=n;i++) if(!in[i]) q.push(i);
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(int i=head[u];i!=-1;i=edge[i].next){
			
			int v=edge[i].to;
			in[v]--;
			if(!in[v]) q.push(v);
			if(sum1[v]==0&&sum2[v]==0){
				sum1[v]=sum1[u];
				sum2[v]=out[u]*sum2[u];
				ll t=gcd(sum1[v],sum2[v]);
				sum1[v]/=t; sum2[v]/=t;
			}
			else{
				sum1[v]=sum1[v]*out[u]*sum2[u]+sum2[v]*sum1[u];
				sum2[v]=sum2[v]*out[u]*sum2[u];
				ll t=gcd(sum2[v],sum1[v]);
				sum1[v]/=t; sum2[v]/=t;
			}
		}
	}
}
int main(){
	memset(head,-1,sizeof(head));
	n=read(); m=read();
	for(int i=1;i<=n;i++){
		out[i]=read();
		for(int j=1;j<=out[i];j++){
			int v=read();
			add(i,v);
			in[v]++;
		}
	}
	for(int i=1;i<=m;i++) sum1[i]=1,sum2[i]=1; 
	toposort();
	for(int i=1;i<=n;i++) if(!out[i]) printf("%lld %lld\n",sum1[i],sum2[i]);
	return 0;
}
2021/8/17 15:38
加载中...