[Algorithm] Prim !

I have recieved emails about bugs of my codes in other blog about Python
This page actually is just the page that I save all my codes. If anyone interesting, you can use codes here.
For tutorials, just browse my other blog. This one is about Prim algorithm:


#include <iostream>
#include <queue>
#include <vector>
#define MAXN 100005 // num of vertexs
#define INFTY 1000000000

using namespace std;
// minimum spanning tree

vector< pair<int,int> > adj[MAXN];//if having many testcases, you should declara adj in procedure main()
priority_queue< pair<int,int> > pq;
int key[MAXN];
int parent[MAXN];
int vis[MAXN];

int main () {
    int N, M, sumTree=0; // N is num of vertexs, M is num of edges
    // vertex is indexed from 0 to N-1
    cin >> N >> M ;
    for (int i = 0; i<M; i++) {
        int a, b, l;
        cin >> a >> b >> l;
        adj[a].push_back (make_pair (b,l));
        adj[b].push_back (make_pair (a,l));
    }

    for (int i = 0; i<N; i++) {
        key[i] = INFTY;
        vis[i] = 0;
    }
     
    key[0] = 0;
    parent[0] = -1;
    pq.push (make_pair (-0,0)); // minus sign to convert largest num to smallest num
    while (!pq.empty ()) {
        int v = pq.top ().second;
        pq.pop ();
        if (vis[v]) continue;
        sumTree += key[v];
        vis[v] = 1;
        for (int i = 0; i<adj[v].size (); i++) {
            if (adj[v][i].second < key[adj[v][i].first] && !vis[adj[v][i].first]) {
                key[adj[v][i].first] = adj[v][i].second;
                parent[adj[v][i].first] = v;
                pq.push (make_pair (-key[adj[v][i].first], adj[v][i].first));
            }
        }
    }
    //print
    cout << sumTree << endl;
    return 0;
}

Không có nhận xét nào:

Đăng nhận xét