prim

#include<iostream> 
#include<cstdio>
#include<queue>
#include<algorithm>

#define ri register int
#define u int
#define NN 5005
#define MM 200005

namespace fast {
    inline u in() {
        u x(0);
        char s=getchar();
        while(s<'0'||s>'9') {
            s=getchar();
        }
        while(s>='0'&&s<='9') {
            x=(x<<1)+(x<<3)+s-'0';
            s=getchar();
        }
        return x;
    }
}

using fast::in;
using std::queue;
using std::pair;

namespace all {
    u N,M,cnt,h[NN];
    struct node {
        u to,next,va;
    } a[MM<<1]; 
    inline void add(const u &x,const u &y,const u &z) {
        a[++cnt].next=h[x],a[cnt].to=y,a[cnt].va=z,h[x]=cnt;
    }
    u ans,num,vt[NN];
    typedef pair<u,u> p;
    std::priority_queue<p, std::vector<p>, std::greater<p> > q;
    void prim(){
        q.push(p(0,1));
        while(num<=N-1){
            u x(q.top().second),d(q.top().first);
            q.pop();
            if(vt[x]) continue;
            ++num,ans+=d,vt[x]=1;
            for(ri i(h[x]);i;i=a[i].next){
                u _y(a[i].to);
                q.push(p(a[i].va,_y));
            }
        }
    }
    inline void solve(){
        N=in(),M=in();
        for(ri i(1);i<=M;++i){
            u _a(in()),_b(in()),_c(in());
            add(_a,_b,_c),add(_b,_a,_c);
        }
        prim();
        printf("%d",ans);
    }
}

int main() {
    //freopen("x.txt","r",stdin);
    all::solve();
}

 

上一篇:算法作业1.1-----用Prim算法构造最小生成树


下一篇:HDU - 4746 Mophues