寻找网站制作公司,wordpress进模板,wordpress 插件查看,番禺区移动端网站制作题目
有一个M行N列的点阵#xff0c;相邻两点可以相连。一条纵向的连线花费一个单位#xff0c;一条横向的连线花费两个单位。某些点之间已经有连线了#xff0c;试问至少还需要花费多少个单位才能使所有的点全部连通。
输入
第一行输入两个正整数m和n。 以下若干行每行…题目
有一个M行N列的点阵相邻两点可以相连。一条纵向的连线花费一个单位一条横向的连线花费两个单位。某些点之间已经有连线了试问至少还需要花费多少个单位才能使所有的点全部连通。
输入
第一行输入两个正整数m和n。 以下若干行每行四个正整数x1,y1,x2,y2表示第x1行第y1列的点和第x2行第y2列的点已经有连线。输入保证|x1-x2||y1-y2|1。 2 2 1 1 2 1
输出
输出使得连通所有点还需要的最小花费。 3 题解
并查集朋友说的反正老师没讲自己想然后就是用lt[(i-1)*nj]表示第i行第j个点的联通分量。然后连一下没连上的就好了。 代码
#includecstdio
using namespace std;
int n,h,k,s,w,x,y,q,lt[1000001],m,x1,y1,x2,y2;
int father(int x)
{return xlt[x]?x:lt[x]father(lt[x]);//并查集
}
int main()
{//freopen(s.txt,r,stdin);//测试用scanf(%d%d,m,n);for (int i1;in*m;i) lt[i]i;while (scanf(%d%d%d%d,x1,y1,x2,y2)4){xfather((x1-1)*ny1);yfather((x2-1)*ny2);if (x!y)//如果不是同一个点{lt[y]x;//联通两个点}}for (int j1;jn;j)//竖连for (int i1;im;i){xfather((i-1)*nj);yfather(i*nj);if (x!y)//如果不是同一个点{lt[y]x;//联通s1;//加}}for (int i1;im;i)//横连for (int j1;jn;j){xfather((i-1)*nj);yfather((i-1)*nj1);if (x!y)//如果不是同一个点{lt[y]x;//联通s2;//加}}printf(%d,s);//输出
}
