<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
Kruskal算法
和上一个问题思路几乎完全一致,只需在未连接的边中用最小生成树算法选边
算法和之前一样,都是Kruskal算法,这次用上了一个矩阵按行存储的技巧,便于在之后运行Kruskal算法
另外,由于边权只有1,2两种,因此对于这种二元属性,可以用类似于电路维修的方法,用双端队列存储所有边,这样就省去了排序的时间
时间复杂度 $O(m*n)$
其中m,n是行数和列数,t是已经存在的边数
至于为什么不用-t,是因为t组已经存在的边在处理输入的时候算进去了
C++ 代码
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <numeric>
#include <functional>
#include <tuple>
#include <vector>
#include <deque>
using namespace std;
using Edge = tuple<int, int, int>;
deque<Edge> edges;
vector<int> origin;
int ans = 0, n, m, sx, ex, sy, ey;
int main() {
//矩阵按行存储,将二维坐标转换为单值
function<int(int, int)> key = [=](int x, int y)->int {
return n * (x - 1) + y - 1;
};
function<int(int)> find = [&find](int x)->int {
if (x != origin[x]) origin[x] = find(origin[x]);
return origin[x];
};
//f来控制操作行为,是0就不用合并,不是0就合并
function<bool(int, int, int)> isConnected = [=](int s, int e, int f)->bool {
int pr = find(s), nx = find(e);
if (pr == nx) return true;
if(f != 0) origin[pr] = nx;
return false;
};
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> m >> n;
origin.resize(m * n);
iota(origin.begin(), origin.end(), 0);
//确定事先连接好的边
while (cin >> sx >> sy >> ex >> ey) {
int s = key(sx, sy), e = key(ex, ey);
isConnected(s, e, 1);
}
int c, r, d;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
//规定只能从一个节点往下,右两个方向上连
c = key(i, j);
//可以纵向连接
if (i != m) {
d = key(i + 1, j);
//纵向权值为1
if (!isConnected(c, d, 0)) edges.push_front({ 1,c,d });
}
//可以横向连接
if (j != n) {
r = key(i, j + 1);
//横向权值为2
if (!isConnected(c, r, 0)) edges.push_back({ 2,c,r });
}
}
}
for (Edge& edge : edges) {
int val = get<0>(edge), s = get<1>(edge), e = get<2>(edge);
if (isConnected(s, e, 1)) continue;
ans += val;
}
cout << ans << endl;
return 0;
}