题目描述
国防部计划用无线网络连接几个边防哨所。 用于构建无线网络的不同通信技术；
每个边防哨所都应配备无线电收发器；有些哨所还可以配备卫星电话。
无论他们相距多远，任何两个配备卫星电话线的哨所（两边都有卫星电话）都可以通话。只有无线电收发器通话的哨所之间的距离不得超过DD，这是受收发器功率限制的。收发器功率越高，通话距离越远DD会更远，但同时价格会更贵。
收发器需要统一购买和安装，所以所有哨所只能选择安装一种型号的收发器。换句话说，每个哨所之间的通话距离都是一样的DD。你的任务是确定收发器必须的最小通话距离DD，使每对哨所之间至少有一条通话路径(直接或间接)。
输入格式
从 wireless.in 输入数据第 1 行，2 个整数SS和PP，SS表示可安装卫星电话的哨所数，PP表示边防哨所的数量。接下里PP行，每行两个整数x，yx，y描述哨所的平面坐标(x, y)(x,y)，以 km 为单位。
输出格式
输出 wireless.out 中
第 1 行，1 个实数DD，表示无线电收发器的最小传输距离，精确到小数点后两位。
输入输出样例
复制
2 4 0 100 0 300 0 600 150 750
复制
212.13
说明/提示
对于20\ %的数据：P = 2，S = 1P=2，S=1
对于另外20\ %的数据：P = 4，S = 2P=4，S=2
对于100\0%数据保证:1 ≤ S ≤ 1001≤S≤100，S < P ≤ 500S<P≤500，0 ≤ x,y ≤ 100000≤x,y≤10000。
#include<bits/stdc .h> using namespace std; int data[100050],x[100050],y[100050]; struct node { double u,v,w; }edge[1000050]; bool cmp(node a,node b) { return a.w<b.w; //从小到大排序 } int find(int a)//并收集的搜索模板； { if(data[a]==a)return a; return data[a]=find(data[a]); } int main() { double res,q,p; cin >> q >> p; int n=1,m=0; for(int i=1;i<=p;i ) { cin >> x[i] >> y[i]; for(int j=1;j<i;j ) { edge[n].u = i; edge[n].v = j; edge[n].w = sqrt((x[i] - x[j]) * (x[i] - x[j]) (y[i] - y[j]) * (y[i] - y[j])); n ; } } for(int i=1;i<=p;i )//循环和初始化； { data[i] = i; } sort(edge 1, edge n 1, cmp);//排序 for(int i=1;i<=n;i ) { if(find(edge[i].u)!=find(edge[i].v)) { data[find(edge[i].u)] = find(edge[i].v); res = edge[i].w; m ; if(m q==p) { printf("%.2lf", res); break; } } } return 0; }题目描述
例如，给出一个无向图，找出最小生成树。如果图不连接，则输出orz。
输入格式
第一行包含两个整数N,MN,M，表示图共有NN个结点和MM条无向边。
接下来MM每行包含三个整数X_i,Y_i,Z_iXi,Yi,Zi，这意味着有一个长度Z_iZi无向边连接点X_i,Y_iXi,Yi。
输出格式
如果图片连接，则输出一个整数表示生成树的最小长度之和。如果图片不连接，则输出orz。
输入输出样例
复制
4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3
复制
7
说明/提示
数据规模：
对于20\ %的数据，N\le 5N≤5，M\le 20M≤20。
对于40\@%的数据，N\le 50N≤50，M\le 2500M≤2500。
对于70\p%的数据，N\le 500N≤500，M\le 10^4M≤104。
对于100\0%的数据：1\le N\le 50001≤N≤5000，1\le M\le 2\times 10^51≤M≤2×105，1\le Z_i \le 10^41≤Zi≤104。
样例解释：
因此，最小生成树的总边权是2 2 3=72 2 3=7。
84已经完成，部分问题正在解决，部分数据仍然存在问题。
#include<bits/stdc .h> using namespace std; int data[5050]; struct node { int u,v,w; }edge[200050]; bool cmp(node a,node b) { return a.w<b.w; //从小到大排序 } int find(int a) { if(data[a]==a)return a; return data[a]=find(data[a]); } int kruskal(int n,int m) { int x=0,y=0; sort(edge 1,edge 1 m,cmp);//sort通过排序，结构体数组的类型不确定CMP来定义 for(int i=1;i<=m;i ) { int a,b; a=find(edge[i].u); b=find(edge[i].v); if(a!=b)///判断是否有闭环 { x =edge[i].w; data[b]=a;//合并两个点到一个集合 y ;///统计合并多少条边 if(y==n-1) { break; } } } return x; } int main() { int n,m,x,y; scanf("%d %d",&n,&m); for(int i=1;i<=n;i ) { data[i]=i;//结构体数组点的循环； } for(int i=1;i<=m;i ) { cin >> edge[i].u >> edge[i].v >> edge[i].w;//边的循环； } x=kruskal(n,m); cout<<x; return 0; } 这两个问题理解相似，可以通过收集和收集来解决。
可应用模板，方便解决此类问题。
#include<bits/stdc .h> using namespace std; int data[5050]; struct node { int u,v,w; }edge[200050]; bool cmp(node a,node b) { return a.w<b.w; //从小到大排序 } int find(int a) { if(data[a]==a)return a; return data[a]=find(data[a]); } int kruskal(int n,int m) { int x=0,y=0; sort(edge 1,edge 1 m,cmp);//sort通过排序，结构体数组的类型不确定CMP来定义 for(int i=1;i<=m;i ) { int a,b; a=find(edge[i].u); b=find(edge[i].v); if(a!=b)///判断是否有闭环 { x =edge[i].w; data[b]=a;//合并两个点到一个集合 y ;///统计合并多少条边 if(y==k) { break; } } } return x; }