P3366 模板最小生成树
题目描述
输入格式
输出格式
输入输出样例
说明/提示
P1991 无线通讯网
题目描述
输入格式
输出格式
输入输出样例
说明/提示
P3366 模板最小生成树
题目描述
例如，给出一个无向图，找出最小生成树。如果图不连接，则输出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。
1.边集数组的边权从小到大排序 2.初始化和收集 3.从头到尾扫描图中所有边: 如果边缘连接的两个节点在同一个集合中跳过这个循环(即已经选择的两个节点的边缘连接) 如果边缘连接的两个节点不在同一集中（即两个节点未连接），则合并两个节点并将边缘权值 加到ans里
#include<bits/stdc .h> using namespace std; int n,m,total; struct edge{ int start; int to; int val; }bian[2000000]; int f[1000000]; int ans; int find(int x)/并收集部分 { if (f[x]==x) return x; else { f[x]=find(f[x]); return f[x]; } } bool cmp(edge a,edge b)///结构体快排，这个排法太棒了！！ { return a.val<b.val; } void kruskal()///最小生成树 { for(int i=1;i<=m;i ) { int u,v; u=find(bian[i].start); v=find(bian[i].to); if(u==v) continue;///判断跳过这个循环，而不是在同一个并集中 ans =bian[i].val;//不在，就加起来 f[u]=v;//合并两个并集 total ; if(total==n-1) break;//形成最小生成树后，退出(以后做的没用) } } int main() { cin>>n>>m; for(int i=1;i<=n;i ) f[i]=i;////初始化父节点为自己 for(int i=1;i<=m;i ) { cin>>bian[i].start>>bian[i].to>>bian[i].val; } sort(bian 1,bian m 1,cmp);///排序边长 kruskal(); if(total==n-1) cout<<ans; else cout<<"orz"; return 0; }P1991 无线通讯网
题目描述
国防部计划用无线网络连接几个边防哨所。 用于构建无线网络的不同通信技术；
每个边防哨所都应配备无线电收发器；有些哨所还可以配备卫星电话。
无论他们相距多远，任何两个配备卫星电话线的哨所（两边都有卫星电话）都可以通话。只有无线电收发器通话的哨所之间的距离不得超过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\%20% 的数据：P = 2，S = 1P=2，S=1
对于另外 20\%20% 的数据：P = 4，S = 2P=4，S=2
对于 100\%100% 的数据保证：1 ≤ S ≤ 1001≤S≤100，S < P ≤ 500S<P≤500，0 ≤ x,y ≤ 100000≤x,y≤10000。
1、赤裸裸的（参考上一题）
2、s！没用！
3、先求一个最小生成树，其中的最大边就是没有所谓的“卫星电话”时的答案了。
4、和最小生成树的区别就是退出条件：最小生成树的模板，有n - 1条边就可以退出了，这里退出条件变成了p - s(p和之前的n是几乎一样的)。（s的唯一一点用处，所以不用考虑那么多卫星电话啥啥的）
（因为有卫星电话的（s个站），人家可以直接联系）
#include<bits/stdc++.h>
using namespace std;
int s,p,n,total,a[100000],b[100000];
struct edge{
int start;
int to;
double val;
}bian[2000000];
int f[1000000];
double ans;
int find(int x)//并查集部分
{
if (f[x]==x)
return x;
else
{
f[x]=find(f[x]);
return f[x];
}
}
bool cmp(edge a,edge b)//结构体排序,这个排法太赞了！！
{
return a.val<b.val;
}
void kruskal()//最小生成树
{
for(int i=1;i<=n;i++)
{
int u,v;
u=find(bian[i].start);
v=find(bian[i].to);
if(u==v)
continue;//判断在不在同一个并查集里面，在就跳过这次循环
f[u]=v;//合并两个并查集
ans=bian[i].val ;
total++;
if(total==p-s)
break;//当形成了最小生成树后，退出（之后做的也没用了）
}
}
int main()
{
cin>>s>>p;
for(int i=1;i<=p;i++)
f[i]=i;//初始化父节点为自己
for(int i=1;i<=p;i++)//存图 !!
{
cin>>a[i]>>b[i];
for(int j=1;j<i;j++)
{
n++;
bian[n].start=i;
bian[n].to=j;
bian[n].val =sqrt((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j]));
}
}
sort(bian+1,bian+n+1,cmp);//排序边长
kruskal();
printf("%.2lf",ans);
return 0;
}