第 11 次实验
A. 岛屿连接
--> 题目描述
小蓝鲸利用假期时间出去旅游。他的第一站到了某个海岛地区，那里正在进行填海造陆工程，让小蓝鲸大开眼界。已知海岛地区大小为 $N\times N$，其中 0 代表海洋，1 代表岛屿。若最多只能将一格 0 变成 1，小蓝鲸想知道经过填海造陆后，这一个区域的最大岛屿面积是多少。注意岛屿只能由上下左右四个方向相连。
--> 输入格式
输入包含 $1+N$ 行：
- 第一行输入 $N$，范围：$1\leq N\leq 10^3 $
- 对于接下来 $N$ 行，每行输入 $N$ 个二进制数。
--> 输出格式
输出包含 $1$ 行，输出填海造陆后最大的岛屿面积。
--> 输入示例
--> 输出示例
Solution
我的想法是分为两步：
-> Step1: 预处理，先根据每个极大连通分量的大小为点附加点权，举个例子：
| 1 1 1 4 4 4
0 0 1 ----> 0 0 4
1 1 0 2 2 0
|
这样在我之后对每个 0 尝试填充时，可以更快地得到周围四格位置连通块的大小
-> Step2: 对每个 0 权值的点尝试填充 1，比较出最优的连通结果
对于 Step1，BFS 就能较好的解决问题，不过我的想法是使用并查集：将二维的点坐标转化为一维的点索引用于并查集存储，unite 采用按大小合并顺便记录集合大小，写起来比较简便，并且时间复杂度 $O(n^2 \alpha (n))$ 可以视为 $O(n^2)$，达到和 BFS 相近的时间开销
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | // 并操作
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(a[i][j] == 1) {
int id = i * n + j;
// 向右合并
if(j + 1 < n && a[i][j + 1] == 1) {
unite(id, id + 1);
}
// 向下合并
if(i + 1 < n && a[i + 1][j] == 1) {
unite(id, id + n);
}
}
}
}
// 查操作
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(a[i][j] == 1) {
int id = i * n + j;
a[i][j] = sz[find(id)];
} else {
a[i][j] = 0;
}
}
}
|
对于 Step2，再进行一轮遍历即可，需要注意下面的特殊情况：
此时对于中间的 0，就不应该累加三次 5 作为连通后的连通大小，之前建立的并查集就可以较好地判断周围的四个数字是否处于同一连通分量，以此去重
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | int ans = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(a[i][j] == 0){
int neighbor[4] = {-1,-1,-1,-1};
int block_size = 1;
if(i > 0) {
block_size += a[i-1][j];
neighbor[0] = find((i-1)*n + j);
}
if(j > 0) {
int id = find(i*n + j - 1);
if(neighbor[0] != id){
block_size += a[i][j-1];
neighbor[1] = id;
}
};
if(i < n-1) {
int id = find((i+1)*n + j);
if(neighbor[0] != id && neighbor[1] != id){
block_size += a[i+1][j];
neighbor[2] = id;
}
}
if(j < n-1) {
int id = find(i*n + j + 1);
if(neighbor[0] != id && neighbor[1] != id && neighbor[2] != id){
block_size += a[i][j+1];
}
}
ans = max(block_size, ans);
}
}
}
cout << ans;
|
最终的程序时间复杂度可以视为 $O(n^2)$
| Solution |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129 | #include <bits/stdc++.h>
using namespace std;
using ll = long long;
// 并查集
int *dsu, *sz;
int find(int x){
return (dsu[x] == x ? x : (dsu[x] = find(dsu[x])));
}
void unite(int x, int y){
x = find(x);
y = find(y);
if (x == y)
return;
if (sz[x] < sz[y])
swap(x, y);
dsu[y] = x;
sz[x] += sz[y];
}
//
// matrix
int a[1001][1001];
void solve(){
int n;
cin >> n;
int nn = n * n;
dsu = new int[nn];
sz = new int[nn];
for (int i = 0; i < nn; i++){
dsu[i] = i;
sz[i] = 1;
}
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
cin >> a[i][j];
}
}
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
if (a[i][j] == 1){
int id = i * n + j;
if (j + 1 < n && a[i][j + 1] == 1){
unite(id, id + 1);
}
if (i + 1 < n && a[i + 1][j] == 1){
unite(id, id + n);
}
}
}
}
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
if (a[i][j] == 1){
int id = i * n + j;
a[i][j] = sz[find(id)];
}
else{
a[i][j] = 0;
}
}
}
int ans = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
if (a[i][j] == 0){
int neighbor[4] = {-1, -1, -1, -1};
int block_size = 1;
if (i > 0){
block_size += a[i - 1][j];
neighbor[0] = find((i - 1) * n + j);
}
if (j > 0){
int id = find(i * n + j - 1);
if (neighbor[0] != id){
block_size += a[i][j - 1];
neighbor[1] = id;
}
};
if (i < n - 1){
int id = find((i + 1) * n + j);
if (neighbor[0] != id && neighbor[1] != id){
block_size += a[i + 1][j];
neighbor[2] = id;
}
}
if (j < n - 1){
int id = find(i * n + j + 1);
if (neighbor[0] != id && neighbor[1] != id && neighbor[2] != id){
block_size += a[i][j + 1];
}
}
ans = max(block_size, ans);
}
}
}
cout << ans;
delete[] dsu;
delete[] sz;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
// cin >> t; // multi testcases
t = 1; // single testcase
while (t--){
solve();
}
return 0;
}
|
B. 小蓝鲸接网线
--> 题目描述
虽然 5G 在中国大陆已经普及，但是蓝鲸大学才刚刚通网。现在需要将 $n$ 台计算机连接起来，一台计算机可以间接地通过其他计算机来和另一台计算机连接。由于网线的价格取决于长度，不同的两台计算机之间的连接费用可能是不同的。
由于蓝鲸大学非常穷，小蓝鲸们不得不靠嚼菜根过日子，而昂贵的布线费用无疑会成为压垮蓝鲸大学财务处的最后一根稻草。因此，校领导希望总的连接费用最省，并且任意两台计算机之间都是连通的（不管是直接还是间接的）。请你编程计算这个最小的费用。
--> 输入描述
输入第一行为两个整数 $n, m(2 \leq n \leq 1 \times 10^5，2 \leq m \leq 3 \times 10^5)$。其中，$n$ 表示计算机总数，$m$ 表示可以建立的连接数。
接下来 $m$ 行，每行三个整数 $a, b, c$，表示在机器 $a$ 和机器 $b$ 之间建立连接的费用是 $c$。（机器从 $1$ 开始标号）
- 题目保证：
- 一定存在可行的连通方案
-
不存在自环（即 $a=b$ 的情况）
-
友情提示：
- 可能存在重边（即 $a$ 和 $b$ 之间可能可以建立多个连接，你应该只关注费用最小的连接）
- long long 你懂的
--> 样例输入
--> 样例输出
Solution
最小生成树模板题，Kruskal 算法和 Prim 算法都能应对重边，考虑到 $2 \leq n \leq 1 \times 10^5，2 \leq m \leq 3 \times 10^5$ 的数据范围，选择 Kruskal 算法
| Solution |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89 | #include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct edge {
int u; int v; int w;
};
// 快速排序模板
bool cmp(edge& a, edge& b){
return a.w < b.w;
}
void swap(edge& a, edge& b) {
edge temp = a;
a = b;
b = temp;
}
void quickSort(edge arr[], int left, int right) {
if (left >= right) return;
int i = left, j = right;
edge pivot = arr[(left + right) / 2];
while (i <= j) {
while (cmp(arr[i], pivot)) i++;
while (cmp(pivot, arr[j])) j--;
if (i <= j) {
swap(arr[i], arr[j]);
i++;
j--;
}
}
quickSort(arr, left, j);
quickSort(arr, i, right);
}
// 并查集
int *dsu;
int find(int x){
return (dsu[x] == x ? x : (dsu[x] = find(dsu[x])) );
}
void unite(int src, int dst) {
dsu[find(src)] = find(dst);
}
//
void solve(){
int n, m; cin >> n >> m;
edge* arr = new edge[m];
dsu = new int[n];
for(int i = 0; i < n; i++) dsu[i] = i;
for(int i = 0; i < m; i++){
int u,v,w; cin>>u>>v>>w;
arr[i] = {u-1,v-1,w};
}
quickSort(arr, 0, m-1);
ll ans = 0; int cnt = 0;
for(int i = 0; i < m; i++){
if(find(arr[i].u) != find(arr[i].v)){
ans += arr[i].w;
cnt++;
unite(arr[i].u, arr[i].v);
if(cnt == n-1) break;
}
}
cout << ((cnt == n-1)? ans : -1);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
// cin >> t; // multi testcases
t = 1; // single testcase
while (t--){
solve();
}
return 0;
}
|
C. 小蓝鲸找最小环
--> 题目描述
现有一个含 $n$ 个顶点的双向图，每个顶点按从 $0$ 到 $n - 1$ 标记。图中的边由二维整数数组 $edges$ 表示，其中 $edges[i] = [u_i, v_i]$ 表示顶点 $u_i$ 和 $v_i$ 之间存在一条边。
请你返回图中最短环的长度。如果不存在环，则返回 $-1$ 。
--> 输入格式
输入共 $1 + m$ 行。
第一行包含 $2$ 个以空格分隔的整数，分别代表顶点数量 $n$ 和边的数量 $m$（根据 $edges$ 数组推算）。
接下来的 $m$ 行，每行包含 2 个以空格分隔的整数 $u_i$ 和 $v_i$，代表数组 $edges$ 中的一条边。
--> 输出格式
1 行。
一个整数，代表图中最短环的长度。如果不存在环，则输出 $-1$。
--> 输入示例
| 7 7
0 1
1 2
2 0
3 4
4 5
5 6
6 3
|
--> 输出示例
解释
图中最短的环为 $0 \to 1 \to 2 \to 0$，长度为 $3$。
--> 输入示例
--> 输出示例
解释
图中不存在环，因此输出 -1。
--> 补充说明
图的性质：每对顶点最多通过一条边连接，并且不存在与自身相连的顶点（无重边、无自环）。
环的定义：环是指以同一节点开始和结束，并且路径中的每条边仅使用一次的路径。
--> 数据范围
顶点数量 $n$ 满足：$2 \le n \le 1000$
边数组 $edges$ 的长度 $m$ 满足：$1 \le m \le 1000$
$edges[i].length == 2$
$0 \le u_i, v_i < n$
$u_i \neq v_i$
Solution
对每个顶点做 BFS 计算最小环，注意双向图指的是无向图
| Solution |
|---|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188 | #include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct AdjNode{
int dest;
int weight;
AdjNode *next;
AdjNode(int d, int w) : dest(d), weight(w), next(nullptr) {}
};
struct Graph{
AdjNode **headers;
int vertices_cnt;
int edges_cnt;
bool directed;
bool weighted;
};
void initGraph(Graph *graph, int n, bool directed = false, bool weighted = false){
graph->vertices_cnt = n;
graph->edges_cnt = 0;
graph->directed = directed;
graph->weighted = weighted;
graph->headers = new AdjNode *[n];
for (int i = 0; i < n; i++)
graph->headers[i] = nullptr;
}
void addEdge(Graph *graph, int src, int dest, int weight = 1){
if (src < 0 || src >= graph->vertices_cnt || dest < 0 || dest >= graph->vertices_cnt){
return;
}
AdjNode *newNode = new AdjNode(dest, weight);
newNode->next = graph->headers[src];
graph->headers[src] = newNode;
if (!graph->directed && src != dest){
AdjNode *reverseNode = new AdjNode(src, weight);
reverseNode->next = graph->headers[dest];
graph->headers[dest] = reverseNode;
}
graph->edges_cnt++;
}
#define MAX_SIZE 10000
class Queue{
private:
int data[MAX_SIZE];
int Front;
int Back;
int count;
public:
Queue(){
Front = 0;
Back = -1;
count = 0;
}
~Queue() {}
void push(int value){
if (!full()){
Back = (Back + 1) % MAX_SIZE;
data[Back] = value;
count++;
}
}
void pop(){
if (!empty()){
Front = (Front + 1) % MAX_SIZE;
count--;
}
}
int front(){
if (!empty())
return data[Front];
else return -1;
}
int back(){
if (!empty())
return data[Back];
else return -1;
}
bool empty(){
return count == 0;
}
bool full(){
return count == MAX_SIZE;
}
int size(){
return count;
}
void clear(){
Front = 0;
Back = -1;
count = 0;
}
};
void solve(){
int n, m;
cin >> n >> m;
Graph *graph = new Graph;
initGraph(graph, n, false, false);
for (int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
addEdge(graph, u, v);
}
int *dist = new int[n];
int *parent = new int[n];
int ans = INT_MAX;
// 遍历每个起点 start
for (int s = 0; s < n; s++){
for (int i = 0; i < n; i++){
dist[i] = -1;
parent[i] = -1;
}
Queue q;
dist[s] = 0;
q.push(s);
// BFS
while (!q.empty()){
int u = q.front();
q.pop();
// 剪枝优化 1
if(dist[u] * 2 >= ans) continue;
AdjNode *cur = graph->headers[u];
while (cur != nullptr){
int v = cur->dest;
// 未访问过的节点，记录信息入队
if (dist[v] == -1){
dist[v] = dist[u] + 1;
parent[v] = u;
q.push(v);
}
// v 是访问过的节点，并且不是 u 的父节点
// 在 s -> u 与 s -> v 的基础上找到了 s -> u -> v -> s 的路径
else if (parent[u] != v){
ans = min(ans, dist[u] + dist[v] + 1);
}
cur = cur->next;
}
}
// 剪枝优化 2
if(ans == 3) break;
}
cout << (ans == INT_MAX ? -1 : ans);
delete graph;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
// cin >> t; // multi testcases
t = 1; // single testcase
while (t--){
solve();
}
return 0;
}
|