社区讨论

链式前向星错了么

P3366【模板】最小生成树参与者 2已保存回复 4

讨论操作

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

当前回复
4 条
当前快照
1 份
快照标识符
@lobs7di9
此快照首次捕获于
2023/10/30 02:05
2 年前
此快照最后确认于
2023/11/04 06:35
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
struct tree{
	int to,next,w;
}ed[200005],Ed[200005];
int m,ji,n,head[200005],ans,fa[200005];
bool cmp(tree a,tree b){
	return a.w<b.w;
}
int find(int k){
	while(k!=fa[k])k=fa[k]=fa[fa[k]];
	return k;
}
void kruskal(){
	sort(ed+1,ed+m+1,cmp);
	for(int i=1;i<=m;i++){
		int x=find(ed[i].next),y=find(ed[i].to);
		if(x==y)continue;
		if(x>y){
			fa[y]=x;
		}
		else 
		fa[x]=y;
		ans+=ed[i].w;
		if(++ji==n-1)return ;
	}
}
bool tong[200005];
void dfs(int now){
	tong[now]=1;
	for(int i=head[now];i;i=Ed[i].next){
		if(!tong[Ed[i].to])dfs(Ed[i].to);
	}
}
void add(int p,int q,int quan){
	Ed[++ji].w=quan;
	Ed[ji].to=q;
	Ed[ji].next=head[p];
	head[p]=ji;
}
int main(){
	cin>>n>>m;
	int cn,cm,cw;
	for(int i=1;i<=m;i++){
		cin>>cn>>cm>>cw;
		ed[i].next=cn,ed[i].to=cm,ed[i].w=cw;
		add(cn,cm,cw);
		add(cm,cn,cw);
	}
	dfs(1);
	ji=0;
	memset(head,0,sizeof(head));
	for(int i=1;i<=n;i++)if(!tong[i]){cout<<"orz";return 0;}
	for(int i=1;i<=n;i++)fa[i]=i;
	kruskal();
	cout<<ans;
}

回复

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

正在加载回复...