生成树（习题）

模板】最小生成树

生成树有两种方法，但是我只会克鲁斯卡尔算法，所以接下来下面的的题目都是按照这个算法来实现的，首先来见一下生么是这个算法，在之前的我写的一篇博客中有题使叫修复公路，其实这一题就是使用了这个算法：用一个结构体记录两个区域的编号，和着两条区域之间道路的价值，再利用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()
{cin>>n>>m;for(int i=1;i<=m;i++){fa[i]=i;}for(int i=1;i<=m;i++){cin>>q[i].x>>q[i].y>>q[i].t;}sort(q+1,q+1+m,cmp);for(int i=1;i<=m;i++){bing(q[i].x,q[i].y,i);//	sum+=q[i].t;if(n==1){cout<<sum<<endl;return 0;}}cout<<"orz"<<endl;return 0;
}

需要注意的是当我们将各个链接成一个整体的时候（即原来有n个整体，后来通过并查集进行链接成一个整体后n就变为1了，这是我们退出的条件）只需要再并函数中设置条件即可（即如果通过查发现这两个节点的根节点不相同，就说明了还没有并在一起，那么就需要将这两区域并在一起，那么整体的数量就变为n-1了）。

完整代码如下：

#include<iostream>
#include<algorithm>
#define N 1002000
#define ll long long
//#define inf 0x7fffffff
using namespace std;
int fa[N];
int n,m;
ll sum=0;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)
{x=cha(x);y=cha(y);if(x==y)return ;else{fa[x]=y;sum+=q[i].t;//这个一点更要放在这个函数里面不然会导致会有多余的数多进行了计算n--;}
}bool cmp(node x,node y)
{return x.t<y.t;
}int main()
{cin>>n>>m;for(int i=1;i<=m;i++){fa[i]=i;}for(int i=1;i<=m;i++){cin>>q[i].x>>q[i].y>>q[i].t;}sort(q+1,q+1+m,cmp);for(int i=1;i<=m;i++){bing(q[i].x,q[i].y,i);//	sum+=q[i].t;if(n==1){cout<<sum<<endl;return 0;}}cout<<"orz"<<endl;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]));}}

这样写就可以保证每一个元素都是不重复的。

那么这个如何判断输出呢？我们只需要将没有安装卫星的地方考虑进去，而安装卫星的地方由于可以无视距离，是所以就可以不用去管，那么我们跳出的条件就算是数量刚好是全部的地方减去可以安装卫星地区的数量就是我们需要的退出条件。

接下来就只需要按照生成树的模板就可以将题目解出来了

#include<iostream>
#include<cmath>
#include<algorithm>
#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 ans=1;int k=0;for (int i = 1; i <= cnt; i++){if(cha(q[i].x)!=cha(q[i].y)){Union(q[i].x,q[i].y);ans=q[i].z;k++;if(k>=p-s){printf("%.2lf\n",ans);return 0;}}}return 0;
}