30分求助
  • 板块P1194 买礼物
  • 楼主tang_mx
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/5/8 13:35
  • 上次更新2023/10/23 16:21:17
查看原帖
30分求助
515833
tang_mx楼主2023/5/8 13:35

蒟蒻实在看不出来哪里出错了,求调

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N=1e5+10;

struct Edge{
	int next,to,val;
}edge[N];

int a,b,num,head[N],ans,fa[N],cnt;

int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}

void add(int u,int v,int value){
	edge[++num].next=head[u];
	edge[num].to=v;
	edge[num].val=value;
	head[u]=num;
}

bool cmp(Edge x,Edge y){
	return x.val<y.val;
}

void Kruskal(){
	sort(edge+1,edge+num+1,cmp);
	for(int i=1;i<=num;i++){
		int u=find(edge[i].next);
		int v=find(edge[i].to);
		if(u==v)continue;
		ans+=edge[i].val;
		fa[v]=u;
	}
}

int main(){
	scanf("%d%d",&a,&b);
	for(int i=1;i<=b;i++){
		fa[i]=i;
		add(0,i,a);
	}
	int w;
	for(int i=1;i<=b;i++){
		for(int j=1;j<=b;j++){
			scanf("%d",&w);
			if(w&&i<j)add(i,j,w);
		}
	}
	Kruskal();
	cout<<ans;
	return 0;
} 
2023/5/8 13:35
加载中...