【BZOJ1083】[SCOI2005]繁忙的都市（最小生成树）

题面

BZOJ
洛谷

题解

模板题。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 350
#define MAXL 10100
inline int read()
{
    int x=0;bool t=false;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
struct edge{int u,v,w;}e[MAXL];
bool operator<(edge a,edge b){return a.w<b.w;}
int n,m,ans,f[MAX];
int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;++i)e[i].u=read(),e[i].v=read(),e[i].w=read();
    sort(&e[1],&e[m+1]);
    for(int i=1;i<=n;++i)f[i]=i;
    for(int i=1;i<=m;++i)
    {
        int u=getf(e[i].u),v=getf(e[i].v);
        if(u==v)continue;ans=e[i].w;
        f[u]=v;
    }
    printf("%d %d\n",n-1,ans);
    return 0;
}

【BZOJ1083】[SCOI2005]繁忙的都市（最小生成树）

原文：https://www.cnblogs.com/cjyyb/p/9739084.html