【高级数据结构】最小生成树

## 1.1 最小生成树是什么？

### 1.2 基本定义

**最小生成树（Minimum Spanning Tree, MST）** 是图论中的一个重要概念。

1. **生成树（Spanning Tree）**： 
  对于一个有 $n$ 个点和 $m$ 条边的连通的无向图，生成树是指包含图中所有顶点 $n$ 的无环连通子图。生成树的边数为 $n - 1$（点数 $-1$），因为它需要连通所有顶点且不形成环。
  
2. **最小生成树（MST）**： 
  在图的所有可能生成树中，边权之和最小的生成树称为 **最小生成树**。

### 1.3 可以解决什么问题？

最小生成树的核心是在连通图中找到连接所有顶点的图（树）并且边权值和最小的方案，其算法核心在于“在保证连通性的前提下找到总成本最小的方案”。因此，它主要解决“连通所有节点”的约束下最小化总代价的场景。

### 1.4 最小生成树有什么优点？

最小生成树顾名思义就是可以让答案最优（权值最大或最小）。

## 2.1 最小生成树的操作：

最小生成树的操作是依靠并查集来实现的（[【高级数据结构】并查集](https://www.luogu.com.cn/article/usjrosd3)）。

### 2.2 操作“流程”

（操作前默认以输入完毕）。

首先，我们先初始化 `fa` 数组。

然后，我们可以将输入的数字从小到大排序（确保最优性）。

接着，我们有两种方式解决问题：

1. #### 2.3 **Kruskal 算法：**
   - 假设现在我们遍历到了第 $i$ 条边。我们先判断这条边要连接的两个点是否没连接过（用并查集找根节点），是的话就将这两个点相连，然后将计数器 `cnt++`（这一步也可以同时将要累加的答案累加等操作），如果选完这条边已经有 `n - 1` 条了，就可以输出答案，`return 0;`。如果没有，就重复这个操作。如果这两个点已经被连接过了，就跳过这条边。
   - 时间复杂度：$O(m\ log\ m)$，适用于稀疏图（比如点数 $10^5$ 个，边数 $10^6$ 等）。
   - 代码实现：
     ```cpp
       for(int i = 1 ; i <= m ; i++){//m 是边的数量。
          if(get(a[i].x) != get(a[i].y)){
              unite(a[i].x,a[i].y);
              cnt++;
              if(cnt == n - 1){
                  cout << a[i].k;
                  return 0;
              }
          }//模板。
      }
     ```
2. #### 2.4 **Prim 算法：**
   -  从任意顶点出发，逐步选择与当前生成树连接的最小权边，增加生成树的点数直到包含所有点即可退出。
   -  时间复杂度：$O(n^2)$，适合于稠密图（比如点数 $10^4$ 个，边数 $10^7$ 等），使用二叉堆（优先队列）优化时间复杂度可以降为 $O((n+m)\ log\ n)$；使用斐波那契堆优化可以降至 $O(n+m\ log\ n)$。（所以没什么用……）
   -  代码实现（不加优化）：
     ```cpp
      int prim(){
        int res = 0;
        for(int i = 0; i < n; i++){
            int t = -1;
            for(int j = 0; j < n; j++){
                if(!st[j] && (t == -1 || dist[j] < dist[t])){//dist 数组用来记录每个点到当前生成树的最短距离，st 数组标记点是否已经在生成树中。
                    t = j;
                }
            }
            if(i && dist[t] == INT_MAX)return INT_MAX;
            if(i)res += dist[t];
            st[t] = true;
            for(int j = 0; j < n; j++){
                dist[j] = min(dist[j], g[t][j]);
            }
        }
        return res;
      }
      //代码摘自AI。
     ```

## 3.1 例题：

[P1547 \[USACO05MAR\] Out of Hay S](https://www.luogu.com.cn/problem/P1547) 板子。

代码实现：

```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,m;

struct node{
    int x,y,k;
}a[2000005];

int fa[2000005];

int get(int x){
    if(fa[x] == x)return x;
    return fa[x] = get(fa[x]);
}

void unite(int x,int y){
    x = get(x);
    y = get(y);
    if(x != y)fa[x] = y;
}

bool cmp(node a,node b){
    return a.k < b.k;
}

int cnt;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)fa[i] = i;
    for(int i = 1 ; i <= m ; i++){
        cin >> a[i].x >> a[i].y >> a[i].k;
    }
    sort(a + 1 , a + 1 + m , cmp);
    for(int i = 1 ; i <= m ; i++){
        if(get(a[i].x) != get(a[i].y)){
            unite(a[i].x,a[i].y);
            cnt++;
            if(cnt == n - 1){
                cout << a[i].k;
                return 0;
            }
        }
    }
    return 0;
}
```

[P2330 \[SCOI2005\] 繁忙的都市](https://www.luogu.com.cn/problem/P2330) 板子（加一个求最值）。

代码实现：

```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,m;

struct node{
    int x,y,k;
}a[2000005];

int fa[2000005];

int get(int x){
    if(fa[x] == x)return x;
    return fa[x] = get(fa[x]);
}

void unite(int x,int y){
    x = get(x);
    y = get(y);
    if(x != y)fa[x] = y;
}

bool cmp(node a,node b){
    return a.k < b.k;
}

int cnt;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)fa[i] = i;
    for(int i = 1 ; i <= m ; i++){
        cin >> a[i].x >> a[i].y >> a[i].k;
    }
    sort(a + 1 , a + 1 + m , cmp);
    for(int i = 1 ; i <= m ; i++){
        if(get(a[i].x) != get(a[i].y)){
            unite(a[i].x,a[i].y);
            cnt++;
            if(cnt == n - 1){
                cout << cnt << " " << a[i].k;
                return 0;
            }
        }
    }
    return 0;
}
```

[P2121 拆地毯](https://www.luogu.com.cn/problem/P2121) 还是板子。

代码实现：

```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,m;
int fa[100005];
struct node{
    int x,y,k;
}a[100005];

int cnt;
int ans;
int get(int x){return fa[x] == x ? x : fa[x] = get(fa[x]);}
void unite(int x,int y){x = get(x),y = get(y);if(x != y)fa[x] = y;}
bool cmp(node x,node y){return x.k > y.k;}
//不推荐这上面这样写。
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int k;
    cin >> n >> m >> k;
    for(int i = 1 ; i <= n ; i++){
        fa[i] = i;
    }
    for(int i = 1 ; i <= m ; i++){
        cin >> a[i].x >> a[i].y >> a[i].k;
    }
    sort(a + 1 , a + 1 + m , cmp);
    for(int i = 1 ; i <= m && cnt < k ; i++){
        if(get(a[i].x) != get(a[i].y)){
            cnt++;
            ans += a[i].k;
            unite(a[i].x,a[i].y);
        }
    }
    cout << ans;
    return 0;
}
```

~~有没有难一点的题啊~~ 有的有的，这样难的题一共有 $3$ 道：

[P1661 扩散](https://www.luogu.com.cn/problem/P1661) 要遍历所有的点的组合，挨个建边，然后才是最小生成树。

代码实现：

```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;

int n;
int fa[100005];

struct node{
	int x,y,k;
}a[100005];

int x[10005],y[10005];

bool cmp(node a,node b){
	return a.k < b.k;
}

int get(int x){
	if(fa[x] == x)return x;
	return fa[x] = get(fa[x]);
}

void unite(int x,int y){
	x = get(x);
	y = get(y);
	if(x != y)fa[x] = y;
}

signed main(){
	cin >> n;
	for(int i = 1 ; i <= n ; i++)fa[i] = i;
	for(int i = 1 ; i <= n ; i++){
		cin >> x[i] >> y[i];
	}
	int m = 0;
	for(int i = 1 ; i <= n ; i++){
		for(int j = i + 1 ; j <= n ; j++){ 
			a[++m] = node{i,j,abs(abs(x[i] - x[j]) + abs(y[i] - y[j]) + 1) / 2};
		}
	}
	int cnt = 0,ans = 0;
	sort(a + 1 , a + 1 + m , cmp);
	for(int i = 1 ; i <= m ; i++){
		if(get(a[i].x) != get(a[i].y)){
			unite(a[i].x,a[i].y);
			cnt++;
			ans = max(ans, a[i].k);
			if(cnt == n - 1){
				cout << ans;
				return 0;
			}
		}
	}
	return 0;
}
```

[P2847 \[USACO16DEC\] Moocast G](https://www.luogu.com.cn/problem/P2847) 也是建边，和上面那题差不多。

代码实现：

```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,m;
int fa[1005];
struct node{
    int x,y;
    int k;
}a[10000005];

int get(int x){
    if(x == fa[x])return x;
    return fa[x] = get(fa[x]);
}

void unite(int x,int y){
    x = get(x);
    y = get(y);
    if(x != y)fa[x] = y;
}

bool cmp(node a,node b){
    return a.k < b.k;
}

int x[100005],y[100005];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1 ; i <= n ; i++)fa[i] = i;
    for(int i = 1 ; i <= n ; i++){
        cin >> x[i] >> y[i];
    }
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= n ; j++){
            if(i != j)a[++m] = node{i,j,(x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])};
        }
    }
    sort(a + 1 , a + 1 + m , cmp);
    int cnt = 0;
    int ans = 0;
    for(int i = 1 ; i <= m ; i++){
        int x = a[i].x,y = a[i].y;
        if(get(x) != get(y)){
            unite(x,y);
            cnt++;
            ans = a[i].k;
            if(cnt == n - 1){
                cout << ans;
                return 0;
            }
        }
    }
    return 0;
}
```

[P2212 \[USACO14MAR\] Watering the Fields S](https://www.luogu.com.cn/problem/P2212) 还是建边，和上面那题差不多。

代码实现：

```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,m;
int fa[2005];

struct node{
    int x,y,k;
}a[4000005];

int get(int x){
    if(fa[x] == x)return x;
    return fa[x] = get(fa[x]);
}

void unite(int x,int y){
    x = get(x);
    y = get(y);
    if(x != y)fa[x] = y;
}

int ans,cnt;

int x[2005],y[2005];

// tanruiqing in 2025.04.21.21:33:04

int c;

bool cmp(node a,node b){
    return a.k < b.k;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> c;
    for(int i = 1 ; i <= n ; i++)fa[i] = i;
    for(int i = 1 ; i <= n ; i++){
        cin >> x[i] >> y[i];
    }
    for(int i = 1 ; i <= n ; i++){
        for(int j = i + 1 ;  j <= n ; j++){
            if((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) >= c)a[++m] = node{i,j,(x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])};
        }
    }
    sort(a + 1 , a + 1 + m , cmp);
    for(int i = 1 ; i <= m ; i++){
        if(get(a[i].x) != get(a[i].y)){
            unite(a[i].x,a[i].y);
            cnt++;
            ans += a[i].k;
            if(cnt == n - 1)break;
        }
    }
    if(cnt == n - 1)cout << ans;
    else cout << -1;
    return 0;
}
```

~~又是真么多重复的题，能不能来点其他的？~~ 有的有的，这样奇奇怪怪的题目一共有 $1$ 道：

[P1550 \[USACO08OCT\] Watering Hole G](https://www.luogu.com.cn/problem/P1550) 用一个虚拟的点 $0$ 来代表从哪里开井，这样就不用最小生成树外面再套一层循环了。

代码实现：

```cpp
#include<bits/stdc++.h>
#define int long long 
using namespace std;

int n,m;

struct node{
	int x,y,k;
};

vector<node> a;

int fa[10005];

int get(int x){
	if(fa[x] == x)return x;
	return fa[x] = get(fa[x]);
}

void unite(int x,int y){
	x = get(x);
	y = get(y);
	fa[x] = y;
}

bool cmp(node a,node b){
	return a.k < b.k;
}

int sum[100005];

signed main(){
	cin >> n;
	for(int i = 0 ; i <= n ; i++)fa[i] = i;
	for(int i = 1,x ; i <= n ; i++){
		cin >> sum[i];
	}
	for(int i = 1 ; i <= n ; i++){
//		unite(0,i);
		a.push_back(node{0,i,sum[i]});
	}
	for(int i = 1 ; i <= n ; i++){
		for(int j = 1,x ; j <= n ; j++){
			cin >> x;
			if(i != j)
				a.push_back(node{i,j,x});
		}
	}
	m = a.size();
	int cnt = 0,ans = 0;
	sort(a.begin() , a.end() , cmp);
	for(int i = 0 ; i < m ; i++){
		if(get(a[i].x) != get(a[i].y)){
			unite(a[i].x,a[i].y);
			cnt++;
			ans += a[i].k;
			if(cnt == n){
				cout << ans;
				return 0;
			}
		}
	}
	return 0;
}
```

### **终极挑战**： [CF1108F MST Unification](https://www.luogu.com.cn/problem/CF1108F)

我们可以跑一遍数组，找到其中权值相同的边，然后将其中的有效边全部连接起来，让计数器++。然后要修改的就是无效边，所以就将有效边从计数器中减去。最后让答案加上计数器，最后输出答案。

代码实现：

```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,m;
int fa[200005];
struct node{
	int x,y,k;
}a[200005];

int get(int x){
	if(fa[x] == x)return x;
	return fa[x] = get(fa[x]);
}

void unite(int x,int y){
	x = get(x);
	y = get(y);
	if(x != y){
		fa[x] = y;
	}
}

bool cmp(node a,node b){
	return a.k < b.k;
}

signed main(){
	int ans = 0,cnt = 0;
	cin >> n >> m;
	for(int i = 1 ; i <= n ; i++){
		fa[i] = i;
	}
	for(int i = 1 ; i <= m ; i++){
		cin >> a[i].x >> a[i].y >> a[i].k;
	}
	sort(a + 1 , a + 1 + m , cmp);
	for(int i = 1 ; i <= m ;){
		int j = i;
		cnt = 0;
		while(a[j].k == a[i].k && j <= m)j++;
		for(int l = i ; l <= j - 1 ; l++){
			if(get(a[l].x) != get(a[l].y)){
				cnt++;
			}
		}
		for(int l = i ; l <= j - 1 ; l++){
			if(get(a[l].x) != get(a[l].y)){
				cnt--;
				unite(a[l].x,a[l].y);
			}
		}
		ans += cnt;
		i = j;
	}
	cout << ans;
	return 0;
}
```

> # $End$