湖南移动官网网站建设,柳州团购汽车网站建设,wordpress某个页面全屏显示,网站作品集模板】最小生成树
生成树有两种方法#xff0c;但是我只会克鲁斯卡尔算法#xff0c;所以接下来下面的的题目都是按照这个算法来实现的#xff0c;首先来见一下生么是这个算法#xff0c;在之前的我写的一篇博客中有题使叫修复公路#xff0c;其实这一题就是使用了这个算…模板】最小生成树
生成树有两种方法但是我只会克鲁斯卡尔算法所以接下来下面的的题目都是按照这个算法来实现的首先来见一下生么是这个算法在之前的我写的一篇博客中有题使叫修复公路其实这一题就是使用了这个算法用一个结构体记录两个区域的编号和着两条区域之间道路的价值再利用sort(排序函数)按照从小到大进行排序有些题目要按照从大到小进行排序利用并查集将各个区域进链接直到所有区域都链接起来假设有n个区域那么这个算法要求只能有n-1条边构成。好了讲完了这个算法的原理就很容易实现了
首先就是并查集的模板查和并的操作。
int cha(int x)
{return fa[x] x ? x : fa[x] cha(fa[x]);
}void Union(int x, int y)
{x cha(x);y cha(y);if (x y) return;if(x!y){fa[x] y;
// cot--;}
}
在是构建主函数
int main()
{cinnm;for(int i1;im;i){fa[i]i;}for(int i1;im;i){cinq[i].xq[i].yq[i].t;}sort(q1,q1m,cmp);for(int i1;im;i){bing(q[i].x,q[i].y,i);// sumq[i].t;if(n1){coutsumendl;return 0;}}coutorzendl;return 0;
}
需要注意的是当我们将各个链接成一个整体的时候即原来有n个整体后来通过并查集进行链接成一个整体后n就变为1了这是我们退出的条件只需要再并函数中设置条件即可即如果通过查发现这两个节点的根节点不相同就说明了还没有并在一起那么就需要将这两区域并在一起那么整体的数量就变为n-1了。
完整代码如下
#includeiostream
#includealgorithm
#define N 1002000
#define ll long long
//#define inf 0x7fffffff
using namespace std;
int fa[N];
int n,m;
ll sum0;struct node
{int x,y,t;
}q[N];int cha(int x)
{return fa[x]x?fa[x]:fa[x]cha(fa[x]);
}void bing(int x,int y,int i)
{xcha(x);ycha(y);if(xy)return ;else{fa[x]y;sumq[i].t;//这个一点更要放在这个函数里面不然会导致会有多余的数多进行了计算n--;}
}bool cmp(node x,node y)
{return x.ty.t;
}int main()
{cinnm;for(int i1;im;i){fa[i]i;}for(int i1;im;i){cinq[i].xq[i].yq[i].t;}sort(q1,q1m,cmp);for(int i1;im;i){bing(q[i].x,q[i].y,i);// sumq[i].t;if(n1){coutsumendl;return 0;}}coutorzendl;return 0;
}
P1991 无线通讯网 这一题确实算比较难以理解我也是看了题解和想了很才明白一点首先我们需要知道的就是这个s究竟是用来干啥的首先我们需要知道当两个地方都安装了卫星就代表着这两个地方就不再收到距离的影响那么为了使这个距离尽量的短所以我们就需要将某两个距离尽量的大的地方安装卫星所以我们就要使用一个结构体数组将两地的编号和距离储存起来对于如何将这两个地方的编号和距离储存起来就需要用到一个嵌套循环
代码如下
for (int i 1; i p; i){for (int j i 1; j p; j){cnt;q[cnt].x i;//这一步和下一行都是为了存编号q[cnt].y j;q[cnt].z sqrt((a[i] - a[j]) * (a[i] - a[j]) (b[i] - b[j]) * (b[i] - b[j]));}}
这样写就可以保证每一个元素都是不重复的。
那么这个如何判断输出呢我们只需要将没有安装卫星的地方考虑进去而安装卫星的地方由于可以无视距离是所以就可以不用去管那么我们跳出的条件就算是数量刚好是全部的地方减去可以安装卫星地区的数量就是我们需要的退出条件。
接下来就只需要按照生成树的模板就可以将题目解出来了
#includeiostream
#includecmath
#includealgorithm
#define N 1009000
using namespace std;int s, p;struct node
{int x, y;double z;
}q[N];int a[N];//记录坐标
int b[N];//记录坐标int cnt 0;//记录长度的组数
int cot;//记录有多少个整体
int fa[N];//定义一个并查集数组int cha(int x)
{return fa[x] x ? x : fa[x] cha(fa[x]);
}void Union(int x, int y)
{x cha(x);y cha(y);if (x y) return;if(x!y){fa[x] y;
// cot--;}
}bool cmp(node x, node y)
{return x.z y.z;
}
int main()
{cin s p;// cot p;for (int i 1; i p; i){cin a[i] b[i];}for (int i 1; i p; i){for (int j i 1; j p; j){cnt;q[cnt].x i;//这一步和下一行都是为了存编号q[cnt].y j;q[cnt].z sqrt((a[i] - a[j]) * (a[i] - a[j]) (b[i] - b[j]) * (b[i] - b[j]));}}for (int i 1; i N - 10; i){fa[i] i;}sort(q 1, q 1 cnt, cmp);double ans1;int k0;for (int i 1; i cnt; i){if(cha(q[i].x)!cha(q[i].y)){Union(q[i].x,q[i].y);ansq[i].z;k;if(kp-s){printf(%.2lf\n,ans);return 0;}}}return 0;
}
