題目描述

現需要在某城市進行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
示例1
輸入：3
3
1 2 3 0
1 3 1 0
2 3 5 0
輸出：4
說明：只需要在1,2以及2,3基站之間鋪設光纖，其成本為3+1=4
示例2
輸入：3
1
1 2 5 0
輸出：-1
說明：3基站無法與其他基站連接，輸出-1
示例3
輸入：3
3
1 2 3 0
1 3 1 0
2 3 5 1
輸出：1
說明：2,3基站已有光纖相連，只有要再1,3站點之間鋪設光纖，其成本為1

解題思路

這個問題可以使用最小生成樹（Minimum Spanning Tree）的思想來解決，Kruskal算法是一種常用的實現方式。下面是解題思路：

• 將所有基站之間的光纖連接按照成本從小到大排序，初始化一個并查集（Union-Find）用于記錄基站的聯通情況。
• 遍歷排序后的光纖連接，逐個連接基站，如果連接后不形成環（即兩個基站不在同一個集合中），則將它們合并，累加連接的成本。
• 當聯通的基站數量達到N-1時，即所有基站都聯通，停止連接。
• 如果最終聯通的基站數量不等于N-1，說明無法建設成功互聯互通的5G網絡，輸出-1；否則輸出累加的連接成本。

題解代碼

Python題解代碼

class Solution:def findCircleNum(self, isConnected: List[List[int]]) -> int:cities = len(isConnected)visited = set()provinces = 0for i in range(cities):if i not in visited:Q = collections.deque([i])while Q:j = Q.popleft()visited.add(j)for k in range(cities):if isConnected[j][k] == 1 and k not in visited:Q.append(k)provinces += 1return provinces

JAVA題解代碼

class Solution {public int findCircleNum(int[][] isConnected) {int ans = 0, n = isConnected.length;boolean[] visit = new boolean[n];for(int i = 0; i < n; ++i){if(!visit[i]){ans++;bfs(i, visit, isConnected);}}return ans;}public void bfs(int i, boolean[] visit, int[][] isConnected){for(int j = 0; j < isConnected.length; ++j){if(isConnected[i][j] == 1 && !visit[j]){visit[j] = true;bfs(j, visit, isConnected);}}}
}

C/C++題解代碼

class Solution {
public:int findCircleNum(vector<vector<int>>& isConnected) {int cities = isConnected.size();vector<int> visited(cities);int provinces = 0;queue<int> Q;for (int i = 0; i < cities; i++) {if (!visited[i]) {Q.push(i);while (!Q.empty()) {int j = Q.front(); Q.pop();visited[j] = 1;for (int k = 0; k < cities; k++) {if (isConnected[j][k] == 1 && !visited[k]) {Q.push(k);}}}provinces++;}}return provinces;}
};

JS題解代碼

var findCircleNum = function(isConnected) {const cities = isConnected.length;const visited = new Set();let provinces = 0;const queue = new Array();for (let i = 0; i < cities; i++) {if (!visited.has(i)) {queue.push(i);while (queue.length) {const j = queue.shift();visited.add(j);for (let k = 0; k < cities; k++) {if (isConnected[j][k] === 1 && !visited.has(k)) {queue.push(k);}}}provinces++;}}return provinces;
};

代碼OJ評判結果

通過測試點

代碼講解

Python題解代碼解析：

這段Python代碼是用于解決一個圖的連通性問題。具體來說，該問題是要求找出城市之間的連通分量個數，其中城市之間的連通關系由isConnected矩陣表示。

• cities表示城市的總數，即矩陣的行數和列數。
• visited是一個集合，用于記錄已經訪問過的城市。
• provinces用于記錄連通分量的數量。
• 通過遍歷城市，對于每個未訪問的城市，使用廣度優先搜索（BFS）的方式找出與該城市直接或間接相連的所有城市，將它們標記為已訪問，并將連通分量數量加一。

最終返回連通分量的數量。

JAVA題解代碼解析：

該Java代碼與Python代碼功能相同，同樣是解決城市之間的連通性問題。主要結構和思路如下：

• findCircleNum方法用于返回連通分量的數量。
• 使用boolean數組visit記錄城市的訪問狀態。
• 使用bfs方法進行廣度優先搜索，找出與當前城市直接或間接相連的所有城市，將它們標記為已訪問。
• 遍歷所有城市，如果某城市未被訪問，則進行廣度優先搜索，同時將連通分量數量加一。

最終返回連通分量的數量。

C/C++題解代碼解析：

這段C++代碼與前兩段代碼實現的功能相同，解決城市之間的連通性問題，使用了BFS算法。

• findCircleNum方法返回連通分量的數量。
• 使用vector<int>數組visited記錄城市的訪問狀態。
• 使用queue<int>數據結構進行廣度優先搜索，找出與當前城市直接或間接相連的所有城市，將它們標記為已訪問。
• 遍歷所有城市，如果某城市未被訪問，則進行廣度優先搜索，同時將連通分量數量加一。

最終返回連通分量的數量。

JS題解代碼解析：

這段JavaScript代碼與前三段代碼實現的功能相同，同樣是解決城市之間的連通性問題，使用了BFS算法。

• findCircleNum函數返回連通分量的數量。
• 使用Set對象visited記錄城市的訪問狀態。
• 使用數組queue進行廣度優先搜索，找出與當前城市直接或間接相連的所有城市，將它們標記為已訪問。
• 遍歷所有城市，如果某城市未被訪問，則進行廣度優先搜索，同時將連通分量數量加一。

最終返回連通分量的數量。

寄語

🚀? 朋友，希望你的華為OD機試就像是一場輕松的技術party！愿你的代碼如同暢快的音符，跳躍在鍵盤上，最后彈奏出一曲高分之歌。加油，你是技術舞臺上的巨星！通過機試，就像是風輕云淡，輕輕松松就把高分收入囊中。祝愿你的編程之旅一路順風，破風前行，每一行代碼都是成功的注腳！🌈💻