为什么会CE啊
  • 板块灌水区
  • 楼主01bit
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/5/5 21:39
  • 上次更新2023/11/4 23:38:45
查看原帖
为什么会CE啊
338147
01bit楼主2021/5/5 21:39
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int max(int a,int b){
	return a>b?a:b;
}

struct Edge{
	int next;
	int v;
}edge[100005];
int cnt=1,head[10005];
void addedge(int u,int v){
	edge[cnt].next=head[u];
	edge[cnt].v=v;
	head[u]=cnt++;
}

struct hn{
	int len,a[100005];
	hn(){
		len=0;
		memset(a,0,sizeof(a));
	}
};
hn operator+(hn a,hn b){
	hn c;
	int len=max(a.len,b.len);
	int x=0;
	for(int i=0;i<len;i++){
		c.a[i]=a.a[i]+b.a[i]+x;
		x=c.a[i]/10;
		c.a[i]%=10;
	}
	if(x)c.a[len++]=x;
	c.len=len;
	return c;
}
hn operator*(hn a,hn b){
	hn c;
	for(int i=0;i<a.len;i++){
		int x=0;
		for(int j=0;j<b.len;j++){
			c.a[i+j]+=a.a[i]*b.a[i]+x;
			x=c.a[i+j]/10;
			c.a[i+j]%=10;
		}
		if(x)c.a[i+b.len]=x;
	}
	if(c.a[a.len+b.len])c.len=a.len+b.len;
	else c.len=a.len+b.len-1;
	return c;
}
bool candiv(hn a,hn b,int i){
	if(a.len-i>b.len)return true;
	for(int j=b.len-1;j>=0;j--)
		if(a.a[i+j]>b.a[i])return true;
		else if(a.a[i+j]<b.a[i])return false;
	return true;
}
hn operator/(hn a,hn b){
	hn c;
	for(int i=a.len-b.len;i>=0;i--){
		while(candiv(a,b,i)){
			for(int j=b.len-1;j>=0;j--){
				if(a.a[i+j]<b.a[j]){
					int k=i+j+1;
					while(a.a[k]==0)k++;
					a.a[k]--;
					a.a[i+j]+=10;
					for(int l=k-1;l>i+j;l--)a.a[l]=9;
				}
				a.a[i+j]=a.a[i+j]-b.a[j];
			}
			c.a[i]++;
		}
	}
	return c;
}
hn operator%(hn a,hn b){
	for(int i=a.len-b.len;i>=0;i--){
		while(candiv(a,b,i)){
			for(int j=b.len-1;j>=0;j--){
				if(a.a[i+j]<b.a[j]){
					int k=i+j+1;
					while(a.a[k]==0)k++;
					a.a[k]--;
					a.a[i+j]+=10;
					for(int l=k-1;l>i+j;l--)a.a[l]=9;
				}
				a.a[i+j]=a.a[i+j]-b.a[j];
			}
		}
	}
	return a;
}
hn gcd(hn a,hn b){
	if(b.len!=0)return gcd(b,a%b);
	return a;
}
struct frac{
	hn p,q;
	frac(){
		p.len=0;
		q.len=1;
		q.a[0]=1;
	}
};
frac operator+(frac a,frac b){
	frac c;
	c.q=a.q*b.q;
	c.p=a.p*b.q+b.p*a.q;
	hn gpq=gcd(c.p,c.q);
	c.p=c.p/gpq;
	c.q=c.q/gpq;
	return c;
}
frac operator/(frac a,int b){
	frac c,b_;
	b_.p.len=1;
	b_.p.a[0]=1;
	b_.q.len=0;
	while(b){
		b_.q.a[b_.q.len++]=b%10;
		b/=10;
	}
	c.p=a.p;
	c.q=a.q*b_.q;
	hn gpq=gcd(c.p,c.q);
	c.p=c.p/gpq;
	c.q=c.q/gpq;
	return c;
}
frac w[10005];
int n,m;
int out[10005],in[10005];
void toposort(){
	queue<int>q;
	for(int i=1;i<=n;i++)if(in[i]==0){q.push(i);w[i].p.len=1;w[i].q.a[0]=1;}
	while(!q.empty()){
		int front=q.front();
		q.pop();
		if(out[front]==0)continue;
		for(int i=head[front];i;i=edge[i].next){
			frac t=w[front]/out[front];
			int x=edge[i].v;
			q.push(x);
			w[x]=w[x]+t;
		}
		w[front]=frac();
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",out+i);
		for(int j=1;j<=out[i];j++){
			int x;
			scanf("%d",&x);
			addedge(i,x);
			in[x]++;
		}
	}
	toposort();
	for(int i=1;i<=n;i++){
		if(out[i]==0){
			frac a=w[i];
			for(int i=a.p.len-1;i>=0;i--)putchar(a.p.a[i]+'0');
			putchar(' ');
			for(int i=a.q.len-1;i>=0;i--)putchar(a.q.a[i]+'0');
			putchar('\n');
		}
	}
	return 0;
}
2021/5/5 21:39
加载中...