Study diary: February 15, 2022

This is simply the minimum spanning tree

There are two algorithms for calculating the minimum spanning tree

kruska Algorithm

and prim Algorithm

I use this topic prim Algorithm

Because this algorithm is similar to that of the shortest path dijkstra The algorithm is very similar to

dijkstra The algorithm calculates all the distances from one point to other points

The minimum spanning tree is the shortest path that can connect all nodes

dijkstra and prim The difference is that

dijkstra Will accumulate the original path to calculate

and prim There is no need to consider starting from the starting point , Every step he took was the shortest way

Finally, I walked through all the nodes . And each node only goes once

The code is as follows

#include<bits/stdc++.h>
using namespace std;
#define N 5003
#define M 200005
#define inf 123456789
struct Node
{
    int v,w,next;
}e[M*2];
int head[N]={0};
int dis[N];// Store final results 
int vis[N];
int top=0;
int n,m;
int add(int a,int b,int c)
{
    top++;
    e[top].v=b;
    e[top].w=c;
    e[top].next=head[a];
    head[a]=top;
}
int finding()
{
    int result=0;
    for(int i=1;i<=n;i++)
    {
        dis[i]=inf;
    }
    dis[1]=0;
    int count=0;
    int present=1;
    while(count++<n)
    {
        int ming=inf;
        for(int i=1;i<=n;i++)
        {
            if(vis[i]==0&&ming>dis[i])
            {
                ming=dis[i];
                present=i;
            }
        }
        if(ming==inf)
        return 0;
        result+=ming;
        for(int i=head[present];i;i=e[i].next)
        {
            int v=e[i].v;
            if(dis[v]>e[i].w&&vis[v]==0)
            dis[v]=e[i].w;
        }
        vis[present]=1;
    }
    return result;
}
int main()
{
    cin>>n>>m;
    int a,b,c;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    int result=finding();
    if(result)
    cout<<result;
    else
    cout<<"orz";
}

Compare what you wrote yesterday dijkstra

#include<iostream>
using namespace std;
long long Max=2147483647;
int point,side,start;
long long result[1000000];
long long book[1000000];
struct Data
{
    int to;
    int length;
    int next;
}data[1000000];
int head[1000000];
int top=0;
int add(int a,int b,int c)
{
    top++;
    data[top].to=b;
    data[top].length=c;
    data[top].next=head[a];
    head[a]=top;
    return 0;
}
int finding(int start)
{
    for(int i=1;i<=point ;i++)
    {
        result[i]=Max;
        book[i]=0;
    }
    result[start]=0;
    int present=start;
    while(book[present]==0)
    {
        book[present]=1;
        long long mining=Max;
        for(int i=head[present];i;i=data[i].next)
        {
            if(book[data[i].to]==0)
            if(result[data[i].to]>result[present]+data[i].length)
            result[data[i].to]=result[present]+data[i].length;
        }
        for(int i=1;i<=point;i++)
        {
            if(book[i]==0)
            if(result[i]<mining)
            {
                mining=result[i];
                present=i;
            }
        }
    }
            return 0;
}

int main()
{
    cin>>point>>side>>start;
    for(int i=1;i<=side;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    finding(start);
    for(int i=1;i<=point ;i++)
    cout<<result[i]<<' ';
}

You will find that the basic architectures are similar

  This topic is also the direct establishment of the minimum spanning tree , Output No s+1 The big data can

Any two points in the title can be directly connected , Use prim The algorithm takes the shortest path every time

The code is as follows

#include<iostream>
#include<math.h>
using namespace std;
#define Max 502
#define inf 123456789
int n,m;
struct Data
{
    int x;
    int y;
    double range;
    bool select;
}data[Max];

double length(int a,int b)
{
    double result;
    int x=data[a].x-data[b].x;
    int y=data[a].y-data[b].y;
    result=sqrt(x*x+y*y);
    return result;
}

// Find the shortest distance corresponding to each point 
int finding()
{
    int count=0;
    int present=1;
    while(count++<m)
    {
        int ming=inf;
        data[present].select=1;
        for(int i=1;i<=m;i++)
        {
            if(data[i].select)
            continue;
            double len=length(present,i);
            if(data[i].range>len)
            {
                data[i].range=len;
            }
        }
        for(int i=1;i<=m;i++)
        {
            if(data[i].select)
            continue;
            if(data[i].range<ming)
            {
                ming=data[i].range;
                present=i;
            }
        }
    }
    // for(int i=1;i<=m;i++)
    // {
    //     for(int j=i+1;j<=m;j++)
    //     {
    //         int len=length(i,j);
    //         if(data[j].range>len)
    //         data[j].range=len;
    //     }
    // }
}

// Sort by distance 
int ranked()
{
    for(int i=1;i<=m;i++)
    {
        int ming=i;
        for(int j=i+1;j<=m;j++)
        if(data[ming].range<data[j].range)
        ming=j;
        Data change;
        {
            change=data[i];
            data[i]=data[ming];
            data[ming]=change;
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        data[i].range=inf;// The initial value of the distance is infinite 
        data[i].select=0;
        cin>>data[i].x>>data[i].y;
    }   
    
    finding();
    ranked();
    // for(int i=1;i<=m;i++)
    // cout<<data[i].range<<endl;

    printf("%.2lf",data[n+1].range);
}

This topic uses prim It's hard to calculate , So we can only use another algorithm

cruska Algorithm

First, we sort the data given by the title according to the beauty degree from big to small

  We choose from the biggest

Then choose the second

  Then choose the third one

  At this time, we found that a ring was formed

First of all, no ring is allowed in the title , Secondly, the minimum spanning tree is not allowed to have rings , If there is a ring , It shows that there is more than one way to go from one point to another , The minimum spanning tree is a path through to the end

So in order to avoid the ring . We use and look up sets

Determine whether the two nodes to be connected are of the same class , If they are of the same kind , It means that the connection will form a ring

You won't , And put them in one category

This is cruska What the algorithm needs to pay attention to

Understand the principle , The implementation code is also relatively simple

#include<iostream>
using namespace std;
#define N 100005

int point ,rug ,needs;// Number of areas , Number of carpets , Reserved number 
int result=0;// Store final results 
int parent[N];// And look up the table 
//  Union checking set 
int check(int start)
{
    if(parent[start]==start)
    return start;
    parent[start]=check(parent[start]);
    return parent[start];
}

struct Data
{
    int a;
    int b;
    int beaut;
}data[N];


int comp(int start ,int end)
{
    int mid=(start+end)/2;
    int a=start;
    int b=mid+1;
    Data shadow[N];
    int len=0;
    while(a<=mid&&b<=end)
    {
        if(data[a].beaut>data[b].beaut)
        shadow[len++]=data[a++];
        else
        shadow[len++]=data[b++];
    }
    while(a<=mid)
    shadow[len++]=data[a++];
    while(b<=end)
    shadow[len++]=data[b++];
    for(int i=0;i<len;i++)
    data[start+i]=shadow[i];
    return 0;
}
int ranked(int start,int end)
{
    if(start>=end)
    return 0;
    int mid=(start+end)/2;
    ranked(start,mid);
    ranked(mid+1,end);
    comp(start,end);
    return 0;
}

int finding()
{
    // Initialize and look up the table 
    for(int i=0;i<=point ;i++)
    parent[i]=i;

    int present=1;
    for(int i=1;i<=needs;i++)
    {
        // Locate blankets that do not form loops 
        while(check(data[present].a)==check(data[present].b))
        present++;
        result+=data[present].beaut;
        parent[check(data[present].a)]=check(data[present].b);
        present++;
    }
    return 0;
}

int main()
{
    cin >>point>>rug>>needs;

    for(int i=1;i<=rug;i++)
    cin >>data[i].a>>data[i].b>>data[i].beaut;
    
    ranked(1,rug);
    finding();
    cout<<result;
}

Because to sort , And the amount of data is quite large , So we need to write a faster sorting method to sort