【华为OD】5G网络建设

发布于：2025-09-10 ⋅ 阅读:(15) ⋅ 点赞:(0)

【华为OD】5G网络建设

题目描述

现需要在某城市进行 5G 网络建设，已经选取 N 个地点设置 5G基站，编号固定为 1 到 N，接下来需要各个基站之间使用光纤进行连接以确保基站能互联互通，不同基站之间架设光纤的成本各不相同，且有些节点之间已经存在光纤相连，请你设计算法，计算出能联通这些基站的最小成本是多少。

注意，基站的联通具有传递性，即基站 A 与基站 B 架设了光纤，基站 B 与基站 C 也架设了光纤，则基站 A 与基站 C 视为可以互相联通。

输入描述

  • 第一行输入表示基站的个数 N，其中 0 < N <= 20
  • 第二行输入表示具备光纤直连条件的基站对的数目 M，其中 0 < M < N*(N - 1) / 2
  • 第三行开始连续输入 M 行数据，格式为 X Y Z P，其中 X Y 表示基站的编号，0 < X <= N，0 < Y <= N 且 X 不等于 Y，Z 表示在 X Y 之间架设光纤的成本，其中 0 < Z < 100，P 表示是否已存在光纤连接，0 表示未连接，1 表示已连接。

输出描述

  • 如果给定条件，可以建设成功互联互通的5G网络，则输出最小的建设成本
  • 如果给定条件，无法建设成功互联互通的5G网络，则输出 -1

示例一

输入：

3
3
1 2 3 0
1 3 1 0
2 3 5 0

输出：

4

说明：
只需要在 1,2 以及 2,3 基站之间铺设光纤，其成本为 3+1=4

示例二

输入：

3
1
1 2 5 0

输出：

-1

说明：
3 基站无法与其他基站连接，输出 -1

示例三

输入：

3
3
1 2 3 0
1 3 1 0
2 3 5 1

输出：

1

说明：
2,3 基站已有光纤相连，只需要再 1,3 站点 2 向铺设，其成本为 1

解题思路

这是一个典型的 最小生成树（MST） 问题。我们需要找到连接所有基站的最小成本。

关键点：

  1. 已经存在的光纤连接（P=1）成本为0，需要建设的光纤连接（P=0）成本为Z
  2. 需要判断是否能够连通所有基站
  3. 如果能连通，求最小生成树的权重和

我将提供两种经典的最小生成树算法：Kruskal算法和Prim算法。

解法一：Kruskal算法（基于边的贪心算法）

Kruskal算法的核心思想是：

  1. 将所有边按权重排序
  2. 使用并查集维护连通性
  3. 依次选择权重最小且不会形成环的边

Java实现

import java.util.*;

public class Solution {
    static class Edge implements Comparable<Edge> {
        int u, v, cost;
        
        public Edge(int u, int v, int cost) {
            this.u = u;
            this.v = v;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Edge other) {
            return Integer.compare(this.cost, other.cost);
        }
    }
    
    static class UnionFind {
        int[] parent, rank;
        int components;
        
        public UnionFind(int n) {
            parent = new int[n + 1];
            rank = new int[n + 1];
            components = n;
            for (int i = 1; i <= n; i++) {
                parent[i] = i;
            }
        }
        
        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        
        public boolean union(int x, int y) {
            int px = find(x), py = find(y);
            if (px == py) return false;
            
            if (rank[px] < rank[py]) {
                parent[px] = py;
            } else if (rank[px] > rank[py]) {
                parent[py] = px;
            } else {
                parent[py] = px;
                rank[px]++;
            }
            components--;
            return true;
        }
        
        public boolean isConnected() {
            return components == 1;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        List<Edge> edges = new ArrayList<>();
        UnionFind uf = new UnionFind(n);
        
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            int p = sc.nextInt();
            
            int cost = (p == 1) ? 0 : z;
            edges.add(new Edge(x, y, cost));
            
            // 如果已经连接，先在并查集中合并
            if (p == 1) {
                uf.union(x, y);
            }
        }
        
        Collections.sort(edges);
        
        int totalCost = 0;
        for (Edge edge : edges) {
            if (uf.union(edge.u, edge.v)) {
                totalCost += edge.cost;
            }
        }
        
        if (uf.isConnected()) {
            System.out.println(totalCost);
        } else {
            System.out.println(-1);
        }
    }
}

Python实现

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.rank = [0] * (n + 1)
        self.components = n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
        elif self.rank[px] > self.rank[py]:
            self.parent[py] = px
        else:
            self.parent[py] = px
            self.rank[px] += 1
        
        self.components -= 1
        return True
    
    def is_connected(self):
        return self.components == 1

def solve():
    n = int(input())
    m = int(input())
    
    edges = []
    uf = UnionFind(n)
    
    for _ in range(m):
        x, y, z, p = map(int, input().split())
        cost = 0 if p == 1 else z
        edges.append((cost, x, y))
        
        # 如果已经连接，先在并查集中合并
        if p == 1:
            uf.union(x, y)
    
    edges.sort()
    
    total_cost = 0
    for cost, u, v in edges:
        if uf.union(u, v):
            total_cost += cost
    
    if uf.is_connected():
        print(total_cost)
    else:
        print(-1)

solve()

C++实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
    int u, v, cost;
    bool operator<(const Edge& other) const {
        return cost < other.cost;
    }
};

class UnionFind {
public:
    vector<int> parent, rank;
    int components;
    
    UnionFind(int n) : parent(n + 1), rank(n + 1, 0), components(n) {
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        
        if (rank[px] < rank[py]) {
            parent[px] = py;
        } else if (rank[px] > rank[py]) {
            parent[py] = px;
        } else {
            parent[py] = px;
            rank[px]++;
        }
        components--;
        return true;
    }
    
    bool isConnected() {
        return components == 1;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<Edge> edges;
    UnionFind uf(n);
    
    for (int i = 0; i < m; i++) {
        int x, y, z, p;
        cin >> x >> y >> z >> p;
        
        int cost = (p == 1) ? 0 : z;
        edges.push_back({x, y, cost});
        
        // 如果已经连接，先在并查集中合并
        if (p == 1) {
            uf.unite(x, y);
        }
    }
    
    sort(edges.begin(), edges.end());
    
    int totalCost = 0;
    for (const Edge& edge : edges) {
        if (uf.unite(edge.u, edge.v)) {
            totalCost += edge.cost;
        }
    }
    
    if (uf.isConnected()) {
        cout << totalCost << endl;
    } else {
        cout << -1 << endl;
    }
    
    return 0;
}

解法二：Prim算法（基于顶点的贪心算法）

Prim算法的核心思想是：

  1. 从任意顶点开始
  2. 每次选择连接已访问顶点和未访问顶点的最小权重边
  3. 直到所有顶点都被访问

Java实现

import java.util.*;

public class Solution2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        // 构建邻接表
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 并查集处理已连接的边
        UnionFind uf = new UnionFind(n);
        
        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            int p = sc.nextInt();
            
            int cost = (p == 1) ? 0 : z;
            graph.get(x).add(new int[]{y, cost});
            graph.get(y).add(new int[]{x, cost});
            
            if (p == 1) {
                uf.union(x, y);
            }
        }
        
        // 使用Prim算法
        boolean[] visited = new boolean[n + 1];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        
        // 从节点1开始
        visited[1] = true;
        for (int[] edge : graph.get(1)) {
            pq.offer(new int[]{edge[0], edge[1]});
        }
        
        int totalCost = 0;
        int edgesUsed = 0;
        
        while (!pq.isEmpty() && edgesUsed < n - 1) {
            int[] current = pq.poll();
            int node = current[0];
            int cost = current[1];
            
            if (visited[node]) continue;
            
            visited[node] = true;
            totalCost += cost;
            edgesUsed++;
            
            for (int[] edge : graph.get(node)) {
                if (!visited[edge[0]]) {
                    pq.offer(new int[]{edge[0], edge[1]});
                }
            }
        }
        
        // 检查是否所有节点都被访问
        boolean allConnected = true;
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                allConnected = false;
                break;
            }
        }
        
        if (allConnected) {
            System.out.println(totalCost);
        } else {
            System.out.println(-1);
        }
    }
    
    static class UnionFind {
        int[] parent, rank;
        
        public UnionFind(int n) {
            parent = new int[n + 1];
            rank = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                parent[i] = i;
            }
        }
        
        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        
        public boolean union(int x, int y) {
            int px = find(x), py = find(y);
            if (px == py) return false;
            
            if (rank[px] < rank[py]) {
                parent[px] = py;
            } else if (rank[px] > rank[py]) {
                parent[py] = px;
            } else {
                parent[py] = px;
                rank[px]++;
            }
            return true;
        }
    }
}

Python实现

import heapq
from collections import defaultdict

def solve_prim():
    n = int(input())
    m = int(input())
    
    # 构建邻接表
    graph = defaultdict(list)
    
    for _ in range(m):
        x, y, z, p = map(int, input().split())
        cost = 0 if p == 1 else z
        graph[x].append((y, cost))
        graph[y].append((x, cost))
    
    # 使用Prim算法
    visited = [False] * (n + 1)
    min_heap = []
    
    # 从节点1开始
    visited[1] = True
    for neighbor, cost in graph[1]:
        heapq.heappush(min_heap, (cost, neighbor))
    
    total_cost = 0
    edges_used = 0
    
    while min_heap and edges_used < n - 1:
        cost, node = heapq.heappop(min_heap)
        
        if visited[node]:
            continue
        
        visited[node] = True
        total_cost += cost
        edges_used += 1
        
        for neighbor, edge_cost in graph[node]:
            if not visited[neighbor]:
                heapq.heappush(min_heap, (edge_cost, neighbor))
    
    # 检查是否所有节点都被访问
    all_connected = all(visited[i] for i in range(1, n + 1))
    
    if all_connected:
        print(total_cost)
    else:
        print(-1)

solve_prim()

C++实现

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    // 构建邻接表
    vector<vector<pair<int, int>>> graph(n + 1);
    
    for (int i = 0; i < m; i++) {
        int x, y, z, p;
        cin >> x >> y >> z >> p;
        
        int cost = (p == 1) ? 0 : z;
        graph[x].push_back({y, cost});
        graph[y].push_back({x, cost});
    }
    
    // 使用Prim算法
    vector<bool> visited(n + 1, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    // 从节点1开始
    visited[1] = true;
    for (auto& edge : graph[1]) {
        pq.push({edge.second, edge.first});
    }
    
    int totalCost = 0;
    int edgesUsed = 0;
    
    while (!pq.empty() && edgesUsed < n - 1) {
        auto current = pq.top();
        pq.pop();
        
        int cost = current.first;
        int node = current.second;
        
        if (visited[node]) continue;
        
        visited[node] = true;
        totalCost += cost;
        edgesUsed++;
        
        for (auto& edge : graph[node]) {
            if (!visited[edge.first]) {
                pq.push({edge.second, edge.first});
            }
        }
    }
    
    // 检查是否所有节点都被访问
    bool allConnected = true;
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            allConnected = false;
            break;
        }
    }
    
    if (allConnected) {
        cout << totalCost << endl;
    } else {
        cout << -1 << endl;
    }
    
    return 0;
}

算法复杂度分析

Kruskal算法：

  • 时间复杂度：O(M log M)，主要是排序的复杂度
  • 空间复杂度：O(N + M)

Prim算法：

  • 时间复杂度：O(M log N)，使用优先队列的复杂度
  • 空间复杂度：O(N + M)

总结

两种算法都能有效解决这个5G网络建设问题：

  1. Kruskal算法更适合边数较少的稀疏图，实现相对简单
  2. Prim算法更适合边数较多的稠密图，在节点数较少时表现更好

对于这道题目，由于N ≤ 20，两种算法的性能差异不大，都能很好地解决问题。关键是要正确处理已存在的光纤连接（成本为0）和判断图的连通性。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布