打倒诶嘿抢榜一 • 4个月前
using namespace std; int n, m; long long ans; int cnt = 1; int fa[N];//定义父节点
struct eage {
int from, to, w;//from我从哪来,to到哪去呢,w我的权值是干嘛的呢
} e[M];
bool mpt(eage a, eage b) {
return a.w < b.w;
}//排序规则
void add(int u, int v, int w) {
e[cnt].from = u;
e[cnt].to = v;
e[cnt].w = w;
cnt++;
} //存储边 void init() {
for (int i = 0; i < N; i++) {
fa[i] = i;
}
} //初始化父节点 int find(int x) {
if (x != fa[x]) {
fa[x] = find(fa[x]);
}
return fa[x];
} //并查集 查 void Union(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
fa[x] = y;
}
} //并查集 并 void kuruskal() {
int k = 0;
sort(e + 1, e + 1 + m, mpt);//排序
for (int i = 1; i <= m; i++) {
if (find(e[i].from) != find(e[i].to)) {
Union(e[i].from, e[i].to);
k++;//边+1
ans += e[i].w;//权值累加
}
if (k == n - 1) {
cout << ans;
break;
}//判断是否构成一棵树
}
if (k != n - 1) {
cout << "orz";
}
}
int main() {
init();
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
}
kuruskal();
return 0;
}
评论:
请先登录,才能进行评论