题意

求一棵最小生成树。

分析

就只是单纯的求一个最小生成树。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 510*510;
#define LL long long
const int inf = 0x3f3f3f3f;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f?-x:x;
}
int fa[N],num=0;
struct Edge{int u,v,w;}e[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
bool cmp(Edge a,Edge b) {return a.w<b.w;}
int main() {
    int T=read();
    while(T--){
        int n=read(),m=read();
        for(int i=0;i<=n;i++)fa[i]=i;
        for(int i=1;i<=m;i++){
            e[i].u=read();e[i].v=read();e[i].w=read();
        }
        sort(e+1,e+1+m,cmp);
        for(int i=1;i<=m;i++){
            if(find(e[i].v)==find(e[i].u))continue;
            fa[find(e[i].v)]=find(e[i].u);
            fa[0]+=e[i].w;
        }
        cout<<"Case #"<<++num<<": "<<fa[0]<<" meters"<<endl;
    }
}