国内外网站开发的现状,浙江建设厅考试成绩查询,佛山制作网站设计报价,网页设计网站网站建设课程设计目录 1.【模板】最小生成树
2.无线通讯网
3.拆地毯
4.营救 1.【模板】最小生成树
P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
如题#xff0c;给出一个无向图#xff0c;求出最小生成树#xff0c;如果该图不连通#xff0c;则…目录 1.【模板】最小生成树
2.无线通讯网
3.拆地毯
4.营救 1.【模板】最小生成树
P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
如题给出一个无向图求出最小生成树如果该图不连通则输出 orz。
输入格式 第一行包含两个整数 N,M表示该图共有 N 个结点和 M 条无向边。
接下来 M 行每行包含三个整数Xi,Yi,Zi表示有一条长度为 Zi 的无向边连接结点 Xi,Yi。
输出格式
如果该图连通则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。
输入输出样例
输入 #1
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出 #1
7
数据范围 1≤N≤50001≤M≤2×10^51≤Zi≤10^4。 既然说是是模版题那么我们直接套用Kruskal算法或者Prim算法的这里我们使用Kruskal算法如果有不清楚这两种算法的可以看我上一篇作品。
这里我们给出核心函数
void Kruskal()
{sort(a1,a1m,cmp);for(int i1;im;i){int fxFind(a[i].x);int fyFind(a[i].y);if(fxfy) continue;pre[fx]fy;ansa[i].w;cnt;if(cntn-1)break; }
}
利用c的sort函数将边按照从小到大排序看便可以完美解决。
下面是完整AC代码
#includebits/stdc.h
using namespace std;
struct node{int x,y,w;
}a[200010];
int n,m,ans0,cnt0;
int pre[6000];
int Find(int x)
{if(pre[x]x) return x;return pre[x]Find(pre[x]);
}
bool cmp(node x,node y)
{return x.wy.w;
}
void Kruskal()
{sort(a1,a1m,cmp);for(int i1;im;i){int fxFind(a[i].x);int fyFind(a[i].y);if(fxfy) continue;//如果在一个集合就跳过 pre[fx]fy;ansa[i].w;cnt;if(cntn-1)//当加入的边等于顶点数-1就停止循环 break; }
}
int main()
{cinnm;for(int i1;in;i){pre[i]i;//初始化 }for(int i1;im;i){cina[i].xa[i].ya[i].w;}Kruskal();//进入核心代码 if(cntn-1)coutansendl;//可以得到答案直接输出 else coutorzendl;//不可以接通 return 0;
}
2.无线通讯网
P1991 无线通讯网 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
国防部计划用无线网络连接若干个边防哨所。2 种不同的通讯技术用来搭建无线网络
每个边防哨所都要配备无线电收发器有一些哨所还可以增配卫星电话。
任意两个配备了一条卫星电话线路的哨所两边都有卫星电话均可以通话无论他们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过 D这是受收发器的功率限制。收发器的功率越高通话距离 D 会更远但同时价格也会更贵。
收发器需要统一购买和安装所以全部哨所只能选择安装一种型号的收发器。换句话说每一对哨所之间的通话距离都是同一个 D。你的任务是确定收发器必须的最小通话距离 D使得每一对哨所之间至少有一条通话路径直接的或者间接的。 输入格式
第一行2 个整数 S 和 PS 表示可安装的卫星电话的哨所数P 表示边防哨所的数量。
接下里 P 行每行两个整数 xy 描述一个哨所的平面坐标(x,y)以 km 为单位。
输出格式
第一行1 个实数 D表示无线电收发器的最小传输距离精确到小数点后两位。 数据范围
1≤S≤100SP≤5000≤x,y≤10000。 这道题我一开始没有看懂到后面经过高人指导才了解我们需要输出最小的传输距离的前提是这些距离可以联通覆盖所有放哨点卫星电话就是不管距离多远也可以传输就不用无线电收发器。
还是使用Kruskal算法我感觉这道题的边排序与Kruskal算法蛮适合。
看数据范围P表示放哨所的数量那我们的边最多是P*P所以给代表边的结构体数组开范围需要开大一些。
边的长度可以利用数学知识勾股定理来求。
double dist(double x1,double y1,double x2,double y2)
{return sqrt(pow(x1-x2,2)pow(y1-y2,2));
}
其他的就是存边操作。 for(int i1;im;i){for(int ji1;jm;j){a[re].xi;a[re].yj;a[re].wdist(x[i],y[i],x[j],y[j]);}}
下面是完整AC代码。
#includebits/stdc.h
using namespace std;
int pre[600];
struct node{int x,y;double w;
}a[300000];
int x[600],y[600],re;
double ans[300000];
double dist(double x1,double y1,double x2,double y2)
{return sqrt(pow(x1-x2,2)pow(y1-y2,2));
}
int Find(int x)
{if(pre[x]x) return x;return pre[x]Find(pre[x]);
}
bool cmp(node k1,node k2)
{return k1.wk2.w;
}
int main()
{int n,m;cinnm;for(int i1;im;i){cinx[i]y[i];pre[i]i;}for(int i1;im;i){for(int ji1;jm;j){a[re].xi;a[re].yj;//存边 a[re].wdist(x[i],y[i],x[j],y[j]);}}sort(a1,a1re,cmp);int cnt0;for(int i1;ire;i){int fxFind(a[i].x);int fyFind(a[i].y);if(fxfy) continue;pre[fx]fy;cnt;if(cntm-n)//减去n是因为多出的n可以使用卫星电话 {printf(%.2lf\n,a[i].w);return 0;}}return 0;
}
3.拆地毯
P2121 拆地毯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
会场上有 n 个关键区域不同的关键区域由 m 条无向地毯彼此连接。每条地毯可由三个整数 u、v、w 表示其中 u 和 v 为地毯连接的两个关键区域编号w 为这条地毯的美丽度。
由于颁奖典礼已经结束铺过的地毯不得不拆除。为了贯彻勤俭节约的原则组织者被要求只能保留至多 K 条地毯且保留的地毯构成的图中任意可互相到达的两点间只能有一种方式互相到达。换言之组织者要求新图中不能有环。现在组织者求助你想请你帮忙算出这至多 K 条地毯的美丽度之和最大为多少。
输入格式
第一行包含三个正整数 n、m、K。
接下来 m 行中每行包含三个正整数 u、v、w。
输出格式
只包含一个正整数表示这 K 条地毯的美丽度之和的最大值。
输入输出样例
输入 #1
5 4 3
1 2 10
1 3 9
2 3 7
4 5 3
输出 #1
22
数据范围
1n,m,k100000 这道题其实就是将边的排序改成从大到小这样才能得到最大美丽度之和。
其他的就和模板体一样。
下面是完整AC代码
#includebits/stdc.h
using namespace std;
struct node{int x,y,w;
}a[100010];
int n,m,ans0,cnt0,k;
int pre[100010];
int Find(int x)
{if(pre[x]x) return x;return pre[x]Find(pre[x]);
}
bool cmp(node x,node y)
{return x.wy.w;
}
void Kruskal()
{sort(a1,a1m,cmp);for(int i1;im;i){int fxFind(a[i].x);int fyFind(a[i].y);if(fxfy) continue;//如果在一个集合就跳过 pre[fx]fy;ansa[i].w;cnt;if(cntk)//当加入的边kbreak; }
}
int main()
{cinnmk;for(int i1;in;i){pre[i]i;//初始化 }for(int i1;im;i){cina[i].xa[i].ya[i].w;}Kruskal();//进入核心代码 coutansendl;return 0;
}
4.营救
P1396 营救 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
妈妈下班回家街坊邻居说小明被一群陌生人强行押上了警车妈妈丰富的经验告诉她小明被带到了 t 区而自己在 s 区。
该市有 m 条大道连接 n 个区一条大道将两个区相连接每个大道有一个拥挤度。小明的妈妈虽然很着急但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 s 至 t 的路线使得经过道路的拥挤度最大值最小。
输入格式
第一行有四个用空格隔开的 nmst其含义见【题目描述】。
接下来 m 行每行三个整数 u,v,w表示有一条大道连接区 u 和区 v且拥挤度为 w。
输出格式
输出一行一个整数代表最大的拥挤度。
输入输出样例
输入 #1
3 3 1 3
1 2 2
2 3 1
1 3 3
输出 #1
2
数据范围
保证 1≤n≤10^41≤m≤2×10^4w≤10^41≤s,t≤n。且从 s 出发一定能到达 t 区。 因为这道题需要的是拥挤度最大值最小所以我们只需输出当s区与t区联通的时候的拥挤度即可。
下面是完整AC代码
#includebits/stdc.h
using namespace std;
struct node{int x,y,w;
}a[20010];
int n,m,ans0,s,e;
int pre[10010];
int Find(int x)
{if(pre[x]x) return x;return pre[x]Find(pre[x]);
}
bool cmp(node x,node y)
{return x.wy.w;
}
int Kruskal()
{sort(a1,a1m,cmp);for(int i1;im;i){int fxFind(a[i].x);int fyFind(a[i].y);if(fxfy) continue;//如果在一个集合就跳过 pre[fx]fy;if(Find(s)Find(e))//此时两区接通 return a[i].w;//因为已经排好序所以这时的拥挤度就是最大拥挤度 }
}
int main()
{cinnmse;for(int i1;in;i){pre[i]i;//初始化 } for(int i1;im;i){cina[i].xa[i].ya[i].w;}coutKruskal()endl;return 0;
}
