Relevant concepts

What is a spanning tree

The spanning tree of a connected graph is a minimal connected subgraph , It contains all the n vertices , But only those that make up a tree n-1 side .

Properties of spanning tree

• A connected graph can have multiple spanning trees .
• All spanning trees of a connected graph contain the same number of vertices and edges .
• There is no ring in the spanning tree .
• Removing any edge from the spanning tree will cause the graph to be disconnected , The least edge property of spanning tree .
• Adding an edge to the spanning tree will form a ring .
• To contain n Connected graph with vertices , The spanning tree contains n A vertex and n-1 side .
• To contain n Undirected complete graphs with vertices contain at most $n^{n-2}$ Every child makes a tree .

What is a minimum spanning tree

The so-called one With weight chart The minimum spanning tree of , It's in the original picture The spanning tree with the smallest weight of the edge , The so-called minimum means that the sum of the weights of the edges is less than or equal to the sum of the weights of the edges of other spanning trees .

Algorithm is introduced

Prim Algorithm

Prim The algorithm adopts a greedy strategy .
Each time the nearest point from the connected part and the edge corresponding to the point are added to the connected part , The connecting part gradually expands , Finally, connect the whole graph , And the sum of side lengths is the smallest .

Kruskal Algorithm

Algorithm ideas ：

• Sort all edges in ascending order according to the weight , Then judge one by one from small to large .
• If this edge does not form a loop with all the previously selected edges , Just choose this side ; conversely , Give up .
• Until have n The connected network of vertices is filtered out n-1 It's up to the edge .
• The filtered edges and all vertices constitute the minimum spanning tree of the connected network .

The method to judge whether a loop will be generated is ： Use and look up sets .

• In the initial state, give each vertex in a different set .
• Traverse each side of the process , Judge whether the two vertices are in a set .
• If the two vertices on the edge are in a set , It means that the two vertices are connected , Don't use this side . If not in a set , This side .

Prim Algorithm for minimum spanning tree

Original link

Title Description

Given a $n$ A little bit $m$ Undirected graph of strip and edge , There may be double edges and self rings in the graph , The edge weight may be negative .
Find the sum of tree edge weights of the minimum spanning tree , If the minimum spanning tree does not exist, output impossible.
Given an undirected graph with weights $G=(V,E)$, among $V$ Represents the set of points in the graph ,$E$ Represents a set of edges in a graph ,
$n=|V|,m=|E|$.
from $V$ All of $n$ A vertex and $E$ in $n-1$ An undirected connected subgraph composed of edges is called $G$ A spanning tree of , The spanning tree in which the sum of the weights of the edges is the smallest is called an undirected graph $G$ The minimum spanning tree of .

Input format

The first line contains two integers $n$ and $m$.
Next m That's ok , Each line contains three integers u,v,w, Indication point u Sum point v There is a weight of w The edge of .

Output format

All in one line , If there is a minimum spanning tree , Then an integer is output , Represents the sum of tree edge weights of the minimum spanning tree , If the minimum spanning tree does not exist, output impossible.

Data range

1≤n≤500,
1≤m≤105,
The absolute values of the edge weights of the edges involved in the graph do not exceed 10000.

sample input ：

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

sample output ：

6

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int inf=0x3f3f3f3f;
const int N=510;
int g[N][N];
int n,m;
int st[N];
int dist[N];

int prim()
{
    
    memset(dist,inf,sizeof dist);
    int res=0;
    for(int i=0;i<n;i++)
    {
    
        int t=-1;
        for(int j=1;j<=n;j++)
        {
    
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
            {
    
                t=j;
            }
        }
        if(i&&dist[t]==inf) return inf;
        if(i)   res+=dist[t];
        for(int j=1;j<=n;j++)
        {
    
            dist[j]=min(dist[j],g[t][j]);
        }
        st[t]=true;
    }
    return res;
}

int main()
{
    
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    memset(g,inf,sizeof g);
    while(m--)
    {
    
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=g[b][a]=min(g[a][b],c);
    }
    int t=prim();
    if(t==inf)  cout<<"impossible"<<'\n';
    else    cout<<t<<'\n';
    return 0;
}

Kruskal Algorithm for minimum spanning tree

Original link

Title Description

Given a n A little bit m Undirected graph of strip and edge , There may be double edges and self rings in the graph , The edge weight may be negative .
Find the sum of tree edge weights of the minimum spanning tree , If the minimum spanning tree does not exist, output impossible.
Given an undirected graph with weights G=(V,E), among V Represents the set of points in the graph ,E Represents a set of edges in a graph ,n=|V|,m=|E|.
from V All of n A vertex and E in n−1 An undirected connected subgraph composed of edges is called G A spanning tree of , The spanning tree in which the sum of the weights of the edges is the smallest is called an undirected graph G The minimum spanning tree of .

Input format

The first line contains two integers n and m.
Next m That's ok , Each line contains three integers u,v,w, Indication point u Sum point v There is a weight of w The edge of .

Output format

All in one line , If there is a minimum spanning tree , Then an integer is output , Represents the sum of tree edge weights of the minimum spanning tree , If the minimum spanning tree does not exist, output impossible.

Data range

1≤n≤105,
1≤m≤2∗105,
The absolute values of the edge weights of the edges involved in the graph do not exceed 1000.

sample input ：

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

sample output ：

6

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int inf=0x3f3f3f3f;
const int N=2e5+10;
int n,m;
struct Node
{
    
    int a,b,w;
    bool operator < (const Node &W) const
    {
    
        return w<W.w;
    }
}edges[N];
int p[N];

int find(int x)
{
    
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main()
{
    
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
    
        cin>>edges[i].a>>edges[i].b>>edges[i].w;
    }
    sort(edges+1,edges+1+m);
    for(int i=1;i<=n;i++)   p[i]=i;
    int res=0,cnt=0;
    for(int i=1;i<=m;i++)
    {
    
        int a=edges[i].a,b=edges[i].b,w=edges[i].w;
        a=find(a),b=find(b);
        if(a!=b)
        {
    
            p[a]=b;
            res+=w;
            cnt++;
        }
    }
    if(cnt<n-1) cout<<"impossible"<<'\n';
    else    cout<<res<<'\n';
    return 0;
}

This document is based on AcWing Make