#P3238. 服务器广播(200分)
-
1000ms
Tried: 69
Accepted: 29
Difficulty: 3
所属公司 :
华为od
服务器广播(200分)
题面描述
给定一个 N∗N 的矩阵,表示 N 台服务器之间的连接关系:
- 如果 matrix[i][j]==1,则表示服务器 i 和服务器 j 直接连接;
- 如果 matrix[i][j]=1,则表示服务器 i 和服务器 j 不直接连接;
- 每台服务器与自身直接连接,即 matrix[i][i]==1;
- 矩阵是对称的,即 matrix[i][j]==matrix[j][i]。
目标:计算最少需要广播的服务器数量,使得每台服务器都能接收到广播信息。
思路
本题可以转化为图论中的“连通分量”问题:
- 将每台服务器看作图中的一个节点。
- 服务器之间的直接连接看作图中的边。
- 需要找到图中的连通分量数量,每个连通分量需要至少一台服务器广播。
因此,解决本题的步骤如下:
- 构建图:根据输入的矩阵,构建图的邻接表或邻接矩阵。
- 遍历图:使用深度优先搜索(DFS)或广度优先搜索(BFS)遍历图,统计连通分量的数量。
- 输出结果:连通分量的数量即为需要广播的服务器数量。
代码分析
-
输入处理:由于题目没有直接给出 N 的值,需要通过读取输入的行数来确定 N。每行包含 N 个数字。
-
图的表示:使用邻接矩阵来表示图,其中
matrix[i][j]表示节点 i 和节点 j 是否直接连接。 -
连通分量的统计:
- 使用一个布尔数组
visited来标记每个节点是否被访问过。 - 遍历每个节点,如果未被访问,则进行一次 DFS/BFS,并将连通分量计数器加一。
- 使用一个布尔数组
-
DFS 实现:
- 递归访问所有与当前节点直接连接且未被访问过的节点。
-
输出结果:最终连通分量的数量即为所需的最少广播服务器数量。
cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
// 读取所有输入
string line;
vector<vector<int>> matrix;
while(getline(cin, line)){
if(line.empty()) continue; // 忽略空行
vector<int> row;
int num;
stringstream ss(line);
while(ss >> num){
row.push_back(num);
}
matrix.push_back(row);
}
int N = matrix.size();
if(N ==0){
cout<<0;
return 0;
}
// 检查每行是否有N个元素
for(auto &row: matrix){
while(row.size() < N){
row.push_back(0); // 补全缺失的0
}
}
// 使用DFS统计连通分量
vector<bool> visited(N, false);
int count =0;
// 定义DFS函数
function<void(int)> dfs = [&](int u)-> void{
visited[u] = true;
for(int v=0; v<N; ++v){
if(matrix[u][v] ==1 && !visited[v]){
dfs(v);
}
}
};
for(int i=0; i<N; ++i){
if(!visited[i]){
count++;
dfs(i);
}
}
cout<<count;
}
python
def count_broadcast_servers(matrix):
N = len(matrix)
visited = [False] * N
count = 0
def dfs(u):
visited[u] = True
for v in range(N):
if matrix[u][v] == 1 and not visited[v]:
dfs(v)
for i in range(N):
if not visited[i]:
count += 1
dfs(i)
return count
# 读取输入
if __name__ == "__main__":
matrix = []
try:
while True:
line = input().strip()
if line:
row = list(map(int, line.split()))
matrix.append(row)
except EOFError:
pass
# 调用函数并输出结果
result = count_broadcast_servers(matrix)
print(result)
java
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static boolean[] visited;
static int count = 0;
public static void dfs(int u, int[][] matrix) {
visited[u] = true;
for (int v = 0; v < matrix.length; v++) {
if (matrix[u][v] == 1 && !visited[v]) {
dfs(v, matrix);
}
}
}
public static int countBroadcastServers(int[][] matrix) {
int N = matrix.length;
visited = new boolean[N];
count = 0;
for (int i = 0; i < N; i++) {
if (!visited[i]) {
count++;
dfs(i, matrix);
}
}
return count;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
List<int[]> matrixList = new ArrayList<>();
while (scanner.hasNextLine()) {
String line = scanner.nextLine().trim();
if (!line.isEmpty()) {
String[] tokens = line.split(" ");
int[] row = new int[tokens.length];
for (int i = 0; i < tokens.length; i++) {
row[i] = Integer.parseInt(tokens[i]);
}
matrixList.add(row);
}
}
int[][] matrix = new int[matrixList.size()][];
for (int i = 0; i < matrixList.size(); i++) {
matrix[i] = matrixList.get(i);
}
// 调用函数并输出结果
int result = countBroadcastServers(matrix);
System.out.println(result);
}
}
题目内容
服务器连接方式包括直接相连,间接相连。A 和 B 直接连接,B 和 C 直接连接,则 A 和 C 间接连接。直接连接和间接连接都可以发送广播。
给出一个 N∗N 数组,代表 N 个服务器,
- matrix[i][j]==1 ,则代表 i 和 j 直接连接;不等于 1 时 ,代表 i 和 j 不直接连接。
- matrix[i][i]==1 , 即自己和自己直接连接。
- matrix[i][j]==matrix[j][i] 。
计算初始需要给几台服务器广播,才可以使每个服务器都收到广播。
输入描述
输入为 N 行,每行有 N 个数字,为 0 或 1 ,由空格分隔,构成 N∗N 的数组, N 的范围为 1<=N<=40
输出描述
输出一个数字,为需要广播的服务器的数量
样例1
输入
1 0 0
0 1 0
0 0 1
输出
3
说明
3 台服务器互不连接,所以需要分别广播这 3 台服务器
样例2
输入
1 1
1 1
输出
1
说明
2 台服务器互相连接,所以只需要广播其中一台服务器