题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 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;
struct Edge
{
	int u,v,w;
}x[200001];
bool cmp(Edge i,Edge j)
{
	return 填空(1);
}
int n,m,fa[5001];
void init()
{
	for(int i=1;i<=n;i++) fa[i] = 填空(2);
}
int find(int t)
{
	if(fa[t]==t) return 填空(3);
	else return 填空(4);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&x[i].u,&x[i].v,&x[i].w);
	
	sort(x+1,填空(5),cmp);
	
	int cnt=0,a,b,ans=0;
	init();
	for(int i=1;i<=m;i++)
	{
		a = find(x[i].u);
		b = find(x[i].v);
		if(a!=b)
		{
			cnt++;
			填空(6);
			ans += 填空(7);
		}
		if(cnt==填空(8))
		{
			printf("%d",填空(9));
			填空(10);
		}
	}
	printf("orz");

	return 0;
}

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

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

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

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

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

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

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

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

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

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