社区讨论

60分,最后四个点全部都只输出0,求大佬调一下

P7113[NOIP2020] 排水系统参与者 3已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@lo8g5egd
此快照首次捕获于
2023/10/27 18:04
2 年前
此快照最后确认于
2023/10/27 18:04
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
#define in read()
#define MAXN 100500
#define int __int128 
using namespace std;

int n,m;
int nex[MAXN],first[MAXN],to[MAXN],rd[MAXN],rdd[MAXN],cd[MAXN],tot=0;
queue<int>q1;

struct node{
	int fz,fm;//分子,分母
}water[MAXN*5];
 
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0' or c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0' and c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
	return x*f;
}

inline void print(int x){if(x>9)print(x/10);putchar(x%10+48);}

inline void addedge(int u,int v){
	rd[v]++;cd[u]++;
	nex[++tot]=first[u];
	first[u]=tot;
	to[tot]=v;
}

inline int getgcd(int x,int y){
	if(!y)return x;
	return getgcd(y,x%y);
}

inline int getlcm(int x,int y){
	return x/getgcd(x,y)*y; 
}

inline void add(int u,int a,int b){//a是加数的分子,b是加数的分母 
	if(!water[u].fm){int gcd=getgcd(a,b);water[u].fm=b/gcd;water[u].fz=a/gcd;return;}
	int c=water[u].fz,d=water[u].fm;//c是被加数的分子,d是被加数的分母 
	int p3=getgcd(b,d);
	int p1=d/p3*a+b/p3*c;
	int p2=getlcm(b,d); 
	int p4=getgcd(p1,p2);
	water[u].fz=p1/p4;
	water[u].fm=p2/p4;
}

inline void topsort(int x){
	q1.push(x);
	water[x].fz=water[x].fm=1; 
	while(!q1.empty()){
		int u=q1.front();q1.pop();
		for(int e=first[u];e;e=nex[e]){
			int v=to[e];rd[v]--;
			int a=water[u].fz,b=water[u].fm*cd[u];
			add(v,a/getgcd(a,b),b/getgcd(a,b)); 
			if(!rd[v])q1.push(v);
		}
	}
}

signed main(){
//	freopen("3.in","r",stdin);
//	freopen("3.out","w",stdout);
	n=in,m=in;
	for(int i=1;i<=n;i++){
		int d=in;
		if(d)for(int j=1;j<=d;j++){int v=in;addedge(i,v);}
	}
	for(int i=1;i<=n;i++)rdd[i]=rd[i];
	for(int i=1;i<=n;i++)
		if(!rdd[i])topsort(i);//是污水接收口 (考虑维护污水数量)
	for(int i=1;i<=n;i++)
		if(!cd[i]){print(water[i].fz);cout<<" ";print(water[i].fm);cout<<'\n';}
		//cout<<water[i].fz<<" "<<water[i].fm<<'\n';
	return 0;
}

回复

5 条回复,欢迎继续交流。

正在加载回复...