AcWing 1144. 网格连接问题（最小生成树 | 克鲁斯卡尔算法题解内容）
发布时间
阅读量：
阅读量
AcWing 1144. 连接格点
发现点多之后就用二维坐标映射到一维，之后就是将所有边都考虑，建图（注意建图get_edge中的先遍历纵向边的小技巧，只能说妙啊妙），之后就是跑克鲁斯卡尔算法，不用担心已经给出的边，因为会提前把他们处理进连通块，这样建最小生成树的时候就不会被这部分权重影响
#include<bits/stdc++.h>
using namespace std;
const int N = 1010, M = N * N;
struct Edge{
int a, b, w;
}e[M * 2]; //无向边，所以要注意开的空间数量
int n, m;
int ids[N][N];
int p[M];
int res;
int k;
int find(int x){
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
void get_edge(){
int dx[4] = {1, 0, -1, 0}, dy[4全部评论 (0)
还没有任何评论哟~