NKCITY - Xây dựng thành phố

Tác giả: skyvn97

Ngôn ngữ: C++

#include<cstdio>
#include<algorithm>
#define MAX   10101
using namespace std;
struct edge {
    edge (){}
    int u,v,w;
    bool operator < (const edge &x) const {
        if (w<x.w) return (true);
        if (w>x.w) return (false);
        return (u+v<x.u+x.v);
    }
};
int up[MAX];
int m,n;
edge e[MAX];
void init(void) {
    scanf("%d",&n);
    scanf("%d",&m);
    int i;
    for (i=1;i<=m;i=i+1) {
        scanf("%d",&e[i].u);
        scanf("%d",&e[i].v);
        scanf("%d",&e[i].w);
    }
    for (i=1;i<=n;i=i+1) up[i]=-1;
    sort(&e[1],&e[m+1]);
}
int find(int x) {
    if (up[x]<0) return (x);
    up[x]=find(up[x]);
    return (up[x]);
}
void join(int a,int b) {
    int x=find(a);
    int y=find(b);
    if (x==y) return;
    up[y]=x;
}
void process(void) {
    int i,c;
    c=0;
    for (i=1;i<=m;i=i+1) {
        if (find(e[i].u)!=find(e[i].v)) {
            join(e[i].u,e[i].v);
            c=c+1;
            if (c==n-1) {
                printf("%d",e[i].w);
                return;
            }
        }
    }
}
int main(void) {
    init();
    process();
    return 0;
}

Download