|
|
# 1615. 最大网络秩
|
|
|
|
|
|
### description：
|
|
|
|
|
|
`n` 座城市和一些连接这些城市的道路 `roads` 共同组成一个基础设施网络。每个 `roads[i] = [ai, bi]` 都表示在城市 `ai` 和 `bi` 之间有一条双向道路。两座不同城市构成的 **城市对** 的 **网络秩** 定义为：与这两座城市 **直接** 相连的道路总数。如果存在一条道路直接连接这两座城市，则这条道路只计算 **一次** 。整个基础设施网络的 **最大网络秩** 是所有不同城市对中的 **最大网络秩** 。给你整数 `n` 和数组 `roads`，返回整个基础设施网络的 **最大网络秩** 。
|
|
|
|
|
|
|
|
|
|
|
|
代码：
|
|
|
|
|
|
```rust
|
|
|
fn main() {
|
|
|
let n:usize = 4;
|
|
|
let roads:Vec<Vec<i32>> = vec![vec![0,1], vec![0,3],vec![1,2], vec![1,3]];
|
|
|
let res = maximal_network_rank(n, &roads);
|
|
|
println!("res is: {}", res);
|
|
|
|
|
|
// for road in &roads{
|
|
|
// for &i in road {
|
|
|
// print!(" {} ", i == 2);
|
|
|
// }
|
|
|
// println!(" ");
|
|
|
// }
|
|
|
println!(" - - - ");
|
|
|
let roads:Vec<&[i32]> = vec![&[0,1], &[0,3], &[1,2], &[1,3]];
|
|
|
let res = maximal_network_rank2(n, &roads);
|
|
|
println!("res is: {}", res);
|
|
|
|
|
|
// for road in &roads{
|
|
|
// for &i in *road{
|
|
|
// print!(" {} ", i==2);
|
|
|
// }
|
|
|
// println!(" ");
|
|
|
// }
|
|
|
|
|
|
|
|
|
// 多维向量
|
|
|
let roads2:Vec<Vec<Vec<i32>>> = vec![vec![vec![0,1], vec![0,3],vec![1,2], vec![1,3]],vec![vec![0,1], vec![0,3],vec![1,2], vec![1,3]]];
|
|
|
for roads in &roads2{
|
|
|
for road in roads{
|
|
|
for &i in road {
|
|
|
print!(" {} ", i == 2);
|
|
|
}
|
|
|
println!(" ");
|
|
|
}
|
|
|
println!(" ");
|
|
|
}
|
|
|
|
|
|
// 多维数组
|
|
|
let roads3: &[&[&[i32]]] = &[&[&[0,1], &[0,3], &[1,2], &[1,3]], &[&[0,1], &[0,3], &[1,2], &[1,3]]];
|
|
|
for &roads in roads3{
|
|
|
for &road in roads{
|
|
|
for &i in road{
|
|
|
print!(" {} ", i==2);
|
|
|
}
|
|
|
}
|
|
|
println!(" ");
|
|
|
}
|
|
|
for roads in roads3{
|
|
|
for road in *roads{
|
|
|
for &i in *road{
|
|
|
print!(" {} ", i==2);
|
|
|
}
|
|
|
}
|
|
|
println!(" ");
|
|
|
}
|
|
|
// 多维数组
|
|
|
let roads4: Vec<&[&[i32]]> = vec![&[&[0,1], &[0,3], &[1,2], &[1,3]], &[&[0,1], &[0,3], &[1,2], &[1,3]]];
|
|
|
for roads in &roads4{
|
|
|
for road in *roads{
|
|
|
for &i in *road{
|
|
|
print!(" {} ", i==2);
|
|
|
}
|
|
|
}
|
|
|
println!(" ");
|
|
|
}
|
|
|
}
|
|
|
|
|
|
fn maximal_network_rank(n:usize, roads:&Vec<Vec<i32>>)->i32{
|
|
|
let mut connect:Vec<Vec<bool>> = vec![vec![false; n]; n];
|
|
|
let mut degree:Vec<i32> = vec![0; n];
|
|
|
|
|
|
for road in roads{
|
|
|
connect[road[0] as usize][road[1] as usize] = true;
|
|
|
connect[road[1] as usize][road[0] as usize] = true;
|
|
|
degree[road[0] as usize] = degree[road[0] as usize]+1;
|
|
|
degree[road[1] as usize] = degree[road[1] as usize]+1;
|
|
|
}
|
|
|
let mut max_rank = 0;
|
|
|
for i in 0..n {
|
|
|
for j in i+1..n{
|
|
|
let rank = degree[i] + degree[j] - (if connect[i][j] { 1 } else { 0 });
|
|
|
max_rank = max_rank.max(rank);
|
|
|
}
|
|
|
}
|
|
|
max_rank
|
|
|
}
|
|
|
|
|
|
fn maximal_network_rank2(n:usize, roads:&[&[i32]])->i32{
|
|
|
let mut connect:Vec<Vec<bool>> = vec![vec![false; n]; n];
|
|
|
let mut degree:Vec<i32> = vec![0; n];
|
|
|
|
|
|
for road in roads{
|
|
|
connect[road[0] as usize][road[1] as usize] = true;
|
|
|
connect[road[1] as usize][road[0] as usize] = true;
|
|
|
degree[road[0] as usize] += 1;
|
|
|
degree[road[1] as usize] += 1;
|
|
|
}
|
|
|
|
|
|
let mut max_rank = 0;
|
|
|
for i in 0..n {
|
|
|
for j in i+1..n{
|
|
|
let rank = degree[i] + degree[j] - if connect[i][j] { 1 } else { 0 };
|
|
|
max_rank = max_rank.max(rank);
|
|
|
}
|
|
|
}
|
|
|
max_rank
|
|
|
}
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
先这样理解，以后遇到再说把，有点乱。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
图：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
接收任何 `i32` 类型的切片，而不仅仅是 `Vec<i32>`写法。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
关于for
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
遍历二维向量（不失去所有权的前提下，取出i32），多维也是如此。
|
|
|
|
|
|
|
|
|
|
|
|
多维：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
`i32` implements [`Add<&i32>`](https://doc.rust-lang.org/std/primitive.i32.html#impl-Add<%26i32>-for-i32), the trait that implements the logic for the `+` operator (and other traits implementing other mathematical operators like `+=` and `*`, see [`std::ops`](https://doc.rust-lang.org/std/ops/index.html) module), but not `PartialEq<&i32>` (the trait used by comparison operators like `>`). Only [`PartialEq`](https://doc.rust-lang.org/std/primitive.i32.html#impl-Add<%26i32>-for-i32) is implemented for `i32`. So you can add, add assign and multiply, etc. `&i32` to a `i32` value, but you can not compare `&i32` with `i32`.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
`for road in &roads` 中，`road` 的类型是 `&&[i32]`，是指向 `&[i32]` 类型的引用。这个引用是从 `roads` 的 `Vec` 中获取的。
|
|
|
|
|
|
而 `for road in roads` 中，`road` 的类型是 `&[i32]`，是 `roads` 中元素的引用，类型为 `&[i32]`。这里的 `roads` 是 `Vec<&[i32]>` 类型的引用，也就是指向 `&[i32]` 类型的引用的引用，即 `&&[i32]` 类型的引用。通过使用 `&` 对 `roads` 进行解引用，可以得到指向 `Vec<&[i32]>>` 类型的引用，即 `&Vec<&[i32]>>`，然后就可以对其进行迭代获取每个 `&[i32]` 类型的引用了。
|
|
|
|
|
|
|
|
|
|
|
|
在 Rust 中，数组或向量的元素可以通过索引访问，无论是使用 `[]` 运算符还是 `get()` 方法。当使用 `[]` 运算符时，Rust 会自动解引用数组或向量的引用，并将其作为指向第一个元素的指针来处理。因此，无论是 `for road in &roads` 还是 `for road in roads`，在使用 `road[0]` 访问数组或向量的第一个元素时，都将自动解引用指向该元素的指针，返回一个 `i32` 类型的值。这是 Rust 语言的自动解引用功能的一部分，它使得代码更加简洁和易读。 |
