解题思路

这是一个最小生成树问题，需要找到连接所有空地的最小生成树，并且要求最长的边最小。这种问题可以使用Kruskal算法的变体来解决。

关键点：

  1. 使用Kruskal算法构建最小生成树
  2. 按照边的长度排序
  3. 使用并查集维护连通性
  4. 找到满足条件的最小最大边

算法步骤：

  1. 对所有边按长度排序
  2. 使用二分查找最小的最大边长度
  3. 检查是否能连通所有点
  4. 返回满足条件的最小值

代码

#include <bits/stdc++.h>
using namespace std;

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;
    int count;
    
public:
    UnionFind(int n) : parent(n), rank(n, 0), count(n) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                swap(rootX, rootY);
            }
            parent[rootY] = rootX;
            if (rank[rootX] == rank[rootY]) {
                rank[rootX]++;
            }
            count--;
        }
    }
    
    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }
    
    int getCount() {
        return count;
    }
};

class Solution {
public:
    int findMinMaxEdge(int n, vector<vector<int>>& edges) {
        // 按边长排序
        sort(edges.begin(), edges.end(), 
             [](const vector<int>& a, const vector<int>& b) {
                 return a[2] < b[2];
             });
        
        int left = 0, right = edges.back()[2];
        int result = right;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            // 检查是否能用不超过mid长度的边连通所有点
            if (canConnect(n, edges, mid)) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
    
private:
    bool canConnect(int n, const vector<vector<int>>& edges, int maxLen) {
        UnionFind uf(n + 1);
        
        // 只使用长度不超过maxLen的边
        for (const auto& edge : edges) {
            if (edge[2] > maxLen) break;
            uf.unite(edge[0], edge[1]);
        }
        
        // 检查是否所有点都连通（除了0）
        int root = uf.find(1);
        for (int i = 2; i <= n; i++) {
            if (uf.find(i) != root) return false;
        }
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> edges(m, vector<int>(3));
    for (int i = 0; i < m; i++) {
        cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
    }
    
    Solution solution;
    cout << solution.findMinMaxEdge(n, edges) << endl;
    
    return 0;
}

import java.util.*;

class UnionFind {
    private int[] parent;
    private int[] rank;
    private int count;
    
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n;
        
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    public void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                int temp = rootX;
                rootX = rootY;
                rootY = temp;
            }
            parent[rootY] = rootX;
            if (rank[rootX] == rank[rootY]) {
                rank[rootX]++;
            }
            count--;
        }
    }
    
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
    
    public int getCount() {
        return count;
    }
}

class Solution {
    private boolean canConnect(int n, int[][] edges, int maxLen) {
        UnionFind uf = new UnionFind(n + 1);
        
        // 只使用长度不超过maxLen的边
        for (int[] edge : edges) {
            if (edge[2] > maxLen) break;
            uf.unite(edge[0], edge[1]);
        }
        
        // 检查是否所有点都连通
        int root = uf.find(1);
        for (int i = 2; i <= n; i++) {
            if (uf.find(i) != root) return false;
        }
        return true;
    }
    
    public int findMinMaxEdge(int n, int[][] edges) {
        // 按边长排序
        Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));
        
        int left = 0, right = edges[edges.length - 1][2];
        int result = right;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (canConnect(n, edges, mid)) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        int[][] edges = new int[m][3];
        for (int i = 0; i < m; i++) {
            edges[i][0] = sc.nextInt();
            edges[i][1] = sc.nextInt();
            edges[i][2] = sc.nextInt();
        }
        
        Solution solution = new Solution();
        System.out.println(solution.findMinMaxEdge(n, edges));
        
        sc.close();
    }
}

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def unite(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x != root_y:
            if self.rank[root_x] < self.rank[root_y]:
                root_x, root_y = root_y, root_x
            self.parent[root_y] = root_x
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1
            self.count -= 1
    
    def is_connected(self, x, y):
        return self.find(x) == self.find(y)
    
    def get_count(self):
        return self.count

class Solution:
    def can_connect(self, n: int, edges: list, max_len: int) -> bool:
        uf = UnionFind(n + 1)
        
        # 只使用长度不超过max_len的边
        for edge in edges:
            if edge[2] > max_len:
                break
            uf.unite(edge[0], edge[1])
        
        # 检查是否所有点都连通
        root = uf.find(1)
        return all(uf.find(i) == root for i in range(2, n + 1))
    
    def find_min_max_edge(self, n: int, edges: list) -> int:
        # 按边长排序
        edges.sort(key=lambda x: x[2])
        
        left, right = 0, edges[-1][2]
        result = right
        
        while left <= right:
            mid = left + (right - left) // 2
            
            if self.can_connect(n, edges, mid):
                result = mid
                right = mid - 1
            else:
                left = mid + 1
        
        return result

def main():
    n, m = map(int, input().split())
    edges = []
    for _ in range(m):
        p, q, k = map(int, input().split())
        edges.append([p, q, k])
    
    solution = Solution()
    print(solution.find_min_max_edge(n, edges))

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：Kruskal算法 + 二分查找
  • 时间复杂度：，其中 是边数， 是最大边长
  • 空间复杂度：，用于并查集数据结构