数据中心

201812-4

这里就是最小生成树的应用

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<string>

using namespace std;

const int maxn=50004;

const int maxm=100005;

int n,m,root;

struct node{

    int from;

    int to;

    int w;

    bool operator<(const node& t)const{

        return w<t.w;

    }

};

node edge[maxm];

int set[maxn];

int find(int x){

    return x==set[x]?set[x]:set[x]=find(set[x]);

}

int kruskal(){

    for(int i=0;i<=n;i++){

        set[i]=i;

    }

    int ans=0;

    for(int j=0;j<m;j++){

        int x=edge[j].from;

        int y=edge[j].to;

        int w=edge[j].w;

        x=find(x),y=find(y);

        if(x!=y){

            set[x]=y;

            ans++;

            if(ans==n-1){

                return w;

            }

        }

    }

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    cin>>n>>m>>root;

    for(int i=0;i<m;i++){

        cin>>edge[i].from>>edge[i].to>>edge[i].w;

    }

    sort(edge,edge+m);

    cout<<kruskal()<<endl;

    //system("pause");

    return 0;

}

巴特西

CCF(数据中心)：最小生成树+kruskal算法

数据中心

201812-4

最新文章

热门文章