很多网站没排名了,宝应县城乡建设局网站,做公司网站需要的资料,专业服务网站建设有一个 m 行 n 列的点阵#xff0c;相邻两点可以相连。
一条纵向的连线花费一个单位#xff0c;一条横向的连线花费两个单位。
某些点之间已经有连线了#xff0c;试问至少还需要花费多少个单位才能使所有的点全部连通。
输入格式
第一行输入两个正整数 m 和 n。
以下若…有一个 m 行 n 列的点阵相邻两点可以相连。
一条纵向的连线花费一个单位一条横向的连线花费两个单位。
某些点之间已经有连线了试问至少还需要花费多少个单位才能使所有的点全部连通。
输入格式
第一行输入两个正整数 m 和 n。
以下若干行每行四个正整数 x1,y1,x2,y2表示第 x1 行第 y1 列的点和第 x2 行第 y2 列的点已经有连线。
输入保证|x1−x2||y1−y2|1。
输出格式
输出使得连通所有点还需要的最小花费。
数据范围
1≤m,n≤1000 0≤已经存在的连线数≤10000
输入样例
2 2
1 1 2 1输出样例
3 解析AcWing 1144. 连接格点算法提高课 - AcWing #includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemapusing namespace std;
typedef long long LL;
const int N 1e310, M 2 * N * N;
int n, m,k;int fa[N * N],idx[N][N];
struct st {int a, b, c;
}e[M];int find(int a) {if (fa[a] a)return fa[a];return fa[a] find(fa[a]);
}void get() {int dx[4] { 1,0,-1,0 }, dy[4] { 0,1,0,-1 }, dw[4] { 1,2,1,2 };for (int z 0; z 2; z) {for (int i 1; i n; i) {for (int j 1; j m; j) {for (int u 0; u 4; u) {if (u % 2 z) {int x i dx[u], y j dy[u], w dw[u];if (x x n y y m) {int a idx[i][j], b idx[x][y];if (a b)e[k] { a,b,w };}}}}}}
}int main() {cin n m;for (int i 1,t1; i n; i) {for (int j 1; j m; j,t) {idx[i][j] t;}}for (int i 1; i n * m; i)fa[i] i;int x1, y, x2, y2;while (cin x1 y x2 y2) {fa[find(idx[x1][y])] find(idx[x2][y2]);}get();int ans 0;for (int i 1; i k; i) {int a find(e[i].a), b find(e[i].b), w e[i].c;if (a ! b) {fa[a] b;ans w;}}cout ans endl;return 0;
}
