题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 $N,M$，表示该图共有 $N$ 个结点和 $M$ 条无向边。

接下来 $M$ 行每行包含三个整数 $X_i,Y_i,Z_i$，表示有一条长度为 $Z_i$ 的无向边连接结点 $X_i,Y_i$。

数据规模

对于 $20\%$ 的数据，$N\le 5$，$M\le 20$。

对于 $40\%$ 的数据，$N\le 50$，$M\le 2500$。

对于 $70\%$ 的数据，$N\le 500$，$M\le 10^4$。

对于 $100\%$ 的数据：$1\le N\le 5000$，$1\le M\le 2\times 10^5$，$1\le Z_i \le 10^4$。

所以最小生成树的总边权为 $2+2+3=7$。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

样例

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

7

样例解释

完善程序

#include<bits/stdc++.h>
using namespace std;
int n,m,tot,h[5001],dis[5001];
bool f[5001];
struct Edge{
	int v,w,next;
}e[400001];
void add(int u,int v,int w){
	e[++tot] = {v,w,h[u]};
	h[u] = tot;
}
long long prim(){
	memset(dis,0x3f,sizeof dis);
	dis[1] = 0;

	int u,v,MIN;
	long long ans=0;
	for(int i=1;i<=n;i++){
		MIN = 0x3f3f3f3f;
		for(int j=1;j<=n;j++){
			if(__填空(1)__){
				u = j;
				MIN = dis[j];
			}
		}

		if(__填空(2)__) return -1;

		ans += __填空(3)__;
		f[u] = true;

		for(int j=h[u];j;j=e[j].next){
			v = __填空(4)__;
			if(!f[v]&&__填空(5)__){
				dis[v] = __填空(6)__;
			}
		}
	}
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);

	int u,v,w;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}

	long long ans=prim();
	if(ans==-1)
		cout<<"orz";
	else
		cout<<ans;

    return 0;
}

填空(1): {{ input(1) }}

填空(2): {{ input(2) }}

填空(3): {{ input(3) }}

填空(4): {{ input(4) }}

填空(5): {{ input(5) }}

填空(6): {{ input(6) }}