Prim algorithm

Minimum spanning tree subproblem:POJ 1287

The priM algorithm of minimum spanning tree has not been learned, and it seems that the most short circuit will also use this idea, so today I learned, looked for a lot of blogs, algorithm diagrams are quite good, but the code implementation is very complex, and finally found a template problem solving blog to read the code implementation.

Prim is a very simple algorithmKeep looking for the current distanceThe generated treeThe smallest node is added to the tree, until all the nodes are in the tree.

Ps: If the algorithm is not clear, take a look at this blog's illustration: Portal.

Know the train of thought, next look at the above template problem, and then carefully, patient simulation of the following code should be no problem.

//https://blog.csdn.net/hesorchen
#include stdio.h
#include iostream
#include algorithm
#include cmath
#include cstring
#include string
#include queue
#include stack
#include list
#include map
#include set
using namespace std;
#define ll long long
#define endl "\n"
#define INF 0x3f3f3f3f
#define mod 1000000007
#define MAX 55

int n, m;
int mp[MAX][MAX]; // Adjacency matrix
int d[MAX];       // Represents the distance between nodes outside each graph and the spanning tree
int t[MAX];       // Record the nodes inside and outside the spanning tree
int prim(a)
{
    int ans = 0;
    d[1] = 0; // Assume node 1 is inside the spanning tree and everything else is outside the tree
    int v;
    while (1)
    {
        v = - 1;
        for (int i = 1; i = n; i++)
        {
            if(! t[i]  (v ==- 1 || d[i]  d[v])) // Find the node v closest to the spanning tree
                v = i;
        }
        if (v == - 1) // If all nodes are already in the spanning tree, the minimum spanning tree has been generated
            break;
        t[v] = 1; // add node v to the node
        ans += d[v];
        for (int i = 1; i = n; i++) // After adding node V to the spanning tree, update the distance between the node connected to v and the spanning tree!!
            d[i] = min(d[i], mp[i][v]);
    }
    return ans;
}
int main(a)
{
    while (cin  n  n)
    {
        cin  m;
        for (int i = 1; i = n; i++) // Initialize the adjacency matrix
        {
            for (int j = 1; j = n; j++)
                if (i == j)
                    mp[i][j] = 0;
                else
                    mp[i][j] = INF;
        }
        while (m--)
        {
            int x, y, z;
            cin  x  y  z; // Enter the update adjacency matrix
            if (mp[x][y]  z)
                mp[x][y] = mp[y][x] = z;
        }
        for (int i = 1; i = n; i++)
            d[i] = INF;
        fill(t, t + MAX, 0);
        cout  prim()  endl;
    }
    return 0;
}
Copy the code

Today's efficiency is low, only look at such an algorithm... (So impetuous!!)