求助
查看原帖
求助
654281
reclusive楼主2023/11/13 08:48

为什么这样写 WA on #7

int kruskal(LL mid){
	vec.clear();
	int cnt=0;
	for(int i=1;i<=m;i++){
		if(a[i].x==1){
			a[i].c+=mid;
		}
	}
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++){
		int x=a[i].x,y=a[i].y;
		int tx=get(x),ty=get(y);
		if(tx!=ty){
			fa[tx]=ty;
			vec.push_back(a[i].id);
			if(x==1){
				cnt++;
			}
		}
	}
	for(int i=1;i<=m;i++){
		if(a[i].x==1){
			a[i].c-=mid;
		}
	}
	return cnt<=K;
}
for(int i=1;i<=m;i++){
	scanf("%d%d%lld",&a[i].x,&a[i].y,&a[i].c);
	if(a[i].x>a[i].y){
		swap(a[i].x,a[i].y);
	}
	a[i].id=i;
}

而这样写 WA on #8

int kruskal(LL mid){
	vec.clear();
	int cnt=0;
	for(int i=1;i<=alen;i++){
		e[i]=a[i];
		e[i].c+=mid;
	}
	for(int i=1;i<=blen;i++){
		e[i+alen]=b[i];
	}
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++){
		int x=e[i].x,y=e[i].y;
		int tx=get(x),ty=get(y);
		if(tx!=ty){
			fa[tx]=ty;
			vec.push_back(e[i].id);
			if(x==1){
				cnt++;
			}
		}
	}
	return cnt<=K;
}
for(int i=1;i<=m;i++){
	int x,y;LL c;scanf("%d%d%lld",&x,&y,&c);
	if(x>y)swap(x,y);
	if(x==1)a[++alen]={x,y,i,c};
	else b[++blen]={x,y,i,c};
}
2023/11/13 08:48
加载中...