Typical applications of minimum spanning tree

Prim&Kruskal One of the core ideas of

Prim Is to choose the distance every time lately The edge of , Then add in ;

Kruskal Is to put the edge right Ascending sort , Connect two at a time Disconnected The point of ;

---

Then how to prove that this selection of edges is correct ？

The proof idea of these two algorithms is the same ;

Suppose the current edge is not selected , Finally got a tree , We add the current side , It must form a ring ; On this ring , It must be possible to find a length Not less than ( Because according to two algorithms , Our side is the smallest ) The side of the current side , We use the current side to Replace Find this side , The result must be It won't get worse ( The worst is the same , It could be smaller );

Example

Kruskal For sparse graphs ,Prim For dense graphs ;

LAN

Portal

Topic

Ideas

Pay attention to this sentence , There will be at most one connection between two computers .

in other words , There may be multiple connected blocks ;

First consider a connected block , Because the connected blocks do not interfere with each other , If there are more than one, we can repeatedly ask for more ;

The maximum to delete , That is, the minimum reserved , That is to find the minimum spanning tree ;

However, this problem has multiple connected blocks , We ask for a " Minimum spanning forest ";

---

Kruskal It has a good property , You ask for a short paragraph , It is also guaranteed to be correct ;

in other words , We don't need to connect the whole graph in the end , In the process , The minimum spanning tree is found in each connected block ;

That is, like a progress bar , As much as you can get, you'll be right ;

Code

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 1e2 + 10;
struct Edge{
    
    int u,v,w;
}e[N << 1];
int p[N];
int find(int x){
    
    if(x == p[x]) return x;
    return p[x] = find(p[x]);
}
void solve(){
    
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;++i) p[i] = i;
    for(int i=1;i<=m;++i){
    
        int u,v,w;
        cin >> u >> v >> w;
        e[i] = {
    u,v,w};
    }
    sort(e+1,e+1+m,[](Edge p,Edge q)->bool{
    
        return p.w < q.w;
    });
    int ans = 0;
    for(int i=1;i<=m;++i){
    
        int u = e[i].u,v = e[i].v,w = e[i].w;
        int pu = find(u),pv = find(v);
        //merge
        if(pu != pv){
    
            p[pu] = pv;
        }
        else{
    
            // To find the minimum spanning tree is to add 
            // This question can be added here directly ;
            // Or calculate the total weight  -  The minimum spanning tree can also 
            ans += w;
        }
    }
    cout << ans << '\n';
}

signed main(){
    
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    solve();
    return 0;
}

A busy city

Portal

Topic

Ideas

From the question stem, we can see , This problem is to find an alternative minimum spanning tree ;

requirement The maximum edge weight is the minimum ;

We found that $Kruskal$ It is also consistent to use the process of this topic ;

Because the edge weights are sorted in ascending order , If two points are disconnected , Then suppose the current side is $u$, We don't choose $u$, And select a back edge $v$ Make these two points connected ;

We found that , We use it $u$ Replace $v$ The result can only be the best ( The maximum edge weight may become smaller , And still connected );

So this topic inspires us Kruskal We can not only find the minimum spanning tree in the traditional sense , You can also find the minimum spanning tree with the minimum maximum edge weight ;

Code

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 1e4 + 10;
struct Edge{
    
    int u,v,w;
}e[N];
int p[N],sz[N];
int find(int x){
    
    if(x == p[x]) return x;
    return p[x] = find(p[x]);
}
void merge(int pu,int pv){
    
    p[pu] = pv;
}
void solve(){
    
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;++i) p[i] = i;
    for(int i=1;i<=m;++i){
    
        int u,v,w;
        cin >> u >> v >> w;
        e[i] = {
    u,v,w};
    }
    sort(e+1,e+1+m,[](Edge p,Edge q)->bool{
    
        return p.w < q.w;
    });
    int ans;
    for(int i=1;i<=m;++i){
    
        int u = e[i].u,v = e[i].v,w = e[i].w;
        int pu = find(u),pv = find(v);
        if(pu == pv) continue;
        merge(pu,pv);
        ans = w;
    }
    cout << n-1 << ' ' << ans << '\n';
}

signed main(){
    
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    solve();
    return 0;
}