最小生成树(模板题:最优布线问题,繁忙的都市,联络员)(C++)

文章目录

• • 序言
  • 正文
  • • First Promble 最优布线问题
    • • 时间限制: 1000 m s 1000 ms 1000ms 空间限制: 262144 K B 262144 KB 262144KB
      • 题目描述
      • 输入
      • 输出
      • 样例输入
      • 样例输出
      • 提示
      • 实现思路
      • Accepted Code
    • Second Problem 繁忙的都市
    • • 时间限制: 1000 ms 空间限制: 262144 KB 具体限制
      • 题目描述
      • 输入
      • 输出
      • 样例输入
      • 样例输出
      • 实现思路
      • Accepted Code
    • Third Problem 联络员
    • • 时间限制: 1000 ms 空间限制: 262144 KB
      • 题目描述
      • 输出 最小的通信费用
      • 样例输入
      • 样例输出
      • 数据范围限制
      • 提示
      • 实现思路
      • Accepted Code

序言

今天老师教了 最小生成树 ,教了两种算法:Prim算法 和 Kruskal算法
Prim算法想快要加堆优化又是这烦人的堆优化，但又一些题目必须用Prim算法,正常Prim算法 时间复杂度为 O ( n 2 ) O(n^2) O(n2),堆优化后是 O ( m l o g m ) O(mlog_m) O(mlogm​)
Kruskal算法 十分好打，还快;实现思路是
将边的权值排序，对边进行枚举，然后加入并查集 时间复杂度为 O ( m l o g m ) O(mlog_m) O(mlogm​).
我将用Kruskal 算法做最小生成树

正文 First Promble 最优布线问题 时间限制: 1000 m s 1000 ms 1000ms 空间限制: 262144 K B 262144 KB 262144KB 题目描述

学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们间有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。
当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。
现在由你负责连接这些计算机，任务是使任意两台计算机都连通（不管是直接的或间接的）。

输入

第一行为整数n ( 2 ≤ n ≤ 100 ) (2le nle 100) (2≤n≤100)，表示计算机的数目。此后的 n n n行，每行 n n n个整数。第 x + 1 x+1 x+1行 y y y列的整数表示直接连接第 x x x台计算机和第 y y y台计算机的费用。

输出

一个整数，表示最小的连接费用。

样例输入

3 3 3
0 0 0 1 1 1 2 2 2
1 1 1 0 0 0 1 1 1
2 2 2 1 1 1 0 0 0

样例输出

2 2 2

提示

（注：表示连接 1 1 1和 2 2 2， 2 2 2和 3 3 3，费用为 2 2 2）

实现思路

这是一个模板最小生成树，自学最小生成树，我推荐这篇;言归正传,这题建议不要用链接矩阵写，用链式前向星写好排序，否则要遍历几遍，可能数据大一点会爆,要了解链式前向星具体去我的**热浪**那篇题解找

Accepted Code

#include
using namespace std;
#define N 101
int qz,fa[N],n,t,ans;
struct no{
	int en,w,ne;
}a[N*N];//链式前向星数组
bool px(no a,no b){//sort排序要用bool
	return a.w//寻找父节点
	return (fa[x]!=x)?(fa[x]=xz(fa[x])):x;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",&qz);
			if(qz){
				a[t++].ne=i;//记录一端节点
				a[t].en=j;//记录另一端节点
				a[t].w=qz;//记录权值
			}
		}
	}
	sort(a,a+t,px);//sort排序
	for(int i=0;i
		int x=xz(a[i].ne),y=xz(a[i].en);//寻找父节点
		if(x!=y){
			ans+=a[i].w;//累加
			if(x 
Second Problem 繁忙的都市 
时间限制: 1000 ms 空间限制: 262144 KB 具体限制 
Go luogu problem
 
题目描述 
城市
    
     
      
       
        C
       
      
      
       C
      
     
    C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市
    
     
      
       
        C
       
      
      
       C
      
     
    C的道路是这样分布的：城市中有
    
     
      
       
        n
       
      
      
       n
      
     
    n个交叉路口，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：
 
改造的那些道路能够把所有的交叉路口直接或间接的连通起来。
 在满足要求
    
     
      
       
        1
       
      
      
       1
      
     
    1的情况下，改造的道路尽量少。
 
在满足要求
    
     
      
       
        1
       
       
        ,
       
       
        2
       
      
      
       1,2
      
     
    1,2的情况下，改造的那些道路中分值最大值尽量小。
 作为市规划局的你，应当作出最佳的决策，选择那些道路应当被修建。
 
输入 
第一行有两个整数
    
     
      
       
        n
       
       
        ,
       
       
        m
       
      
      
       n,m
      
     
    n,m表示城市有
    
     
      
       
        n
       
      
      
       n
      
     
    n个交叉路口，
    
     
      
       
        m
       
      
      
       m
      
     
    m条道路。接下来
    
     
      
       
        m
       
      
      
       m
      
     
    m行是对每条道路的描述，
    
     
      
       
        u
       
       
        ,
       
       
        v
       
       
        ,
       
       
        c
       
      
      
       u, v, c
      
     
    u,v,c表示交叉路口
    
     
      
       
        u
       
      
      
       u
      
     
    u和
    
     
      
       
        v
       
      
      
       v
      
     
    v之间有道路相连，分值为
    
     
      
       
        c
       
      
      
       c
      
     
    c。
    
     
      
       
        (
       
       
        1
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        300
       
       
        ，
       
       
        1
       
       
        ≤
       
       
        c
       
       
        ≤
       
       
        10000
       
       
        )
       
      
      
       (1≤n≤300，1≤c≤10000)
      
     
    (1≤n≤300，1≤c≤10000)
 
输出 
两个整数s, max，表示你选出了几条道路，分值最大的那条道路的分值是多少。
 
样例输入 
 
 
4 5
 1 2 3
 1 4 5
 2 4 7
 2 3 6
 3 4 8
 
 
样例输出 
3 6
 
实现思路 
这道题甚至比上一道题简单，这里可以直接用链式前向星保存，不像第一题绕弯子用链接矩阵输入，这里学过最小生成树的人就知道，这题是高诉我们最小生成树的边都比其他边小
 
Accepted Code 
#include
using namespace std;
#define N 300
int qz,fa[N],n,t,ans,maxn=0xf7777777;//maxn为负数就行
struct no{
	int en,w,ne;
}a[N*N];
bool px(no a,no b){
	return a.w
	return (fa[x]!=x)?(fa[x]=xz(fa[x])):x;
}
int main(){
	scanf("%d%d",&n,&t);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=t;i++){
		scanf("%d%d%d",&a[i].ne,&a[i].en,&a[i].w);//直接用链式前向星读入
	}
	sort(a,a+t,px);
	for(int i=0;i
		int x=xz(a[i].ne),y=xz(a[i].en);
		if(x!=y){
			maxn=max(maxn,a[i].w);//更新maxn
			if(x 
Third Problem 联络员 
时间限制: 1000 ms 空间限制: 262144 KB 
Go ACwing Problem(需要买课程,只找到这一个)
 
题目描述 

    
     
      
       
        T
       
       
        y
       
       
        v
       
       
        j
       
      
      
       Tyvj
      
     
    Tyvj 已经
    
     
      
       
        一
       
      
      
       一
      
     
    一岁了，网站也由最初的几个用户增加到了上万个用户，随着 
    
     
      
       
        T
       
       
        y
       
       
        v
       
       
        j
       
      
      
       Tyvj
      
     
    Tyvj 网站的逐步壮大，管理员的数目也越来越多，现在你身为 
    
     
      
       
        T
       
       
        y
       
       
        v
       
       
        j
       
      
      
       Tyvj
      
     
    Tyvj 管理层的联络员，希望你找到一些通信渠道，使得管理员两两都可以联络（直接或者是间接都可以）。
    
     
      
       
        T
       
       
        y
       
       
        v
       
       
        j
       
      
      
       Tyvj
      
     
    Tyvj 是一个公益性的网站，没有过多的利润，所以你要尽可能的使费用少才可以。
 目前你已经知道，
    
     
      
       
        T
       
       
        y
       
       
        v
       
       
        j
       
      
      
       Tyvj
      
     
    Tyvj 的通信渠道分为两大类，一类是必选通信渠道，无论价格多少，你都需要把所有的都选择上；还有一类是选择性的通信渠道，你可以从中挑选一些作为最终管理员联络的通信渠道。数据保证给出的通行渠道可以让所有的管理员联通。
 
输入
 第一行 
    
     
      
       
        n
       
       
        ，
       
       
        m
       
      
      
       n，m
      
     
    n，m 表示 
    
     
      
       
        T
       
       
        y
       
       
        v
       
       
        j
       
      
      
       Tyvj
      
     
    Tyvj 一共有 
    
     
      
       
        n
       
      
      
       n
      
     
    n 个管理员，有 
    
     
      
       
        m
       
      
      
       m
      
     
    m 个通信渠道
 第二行到 
    
     
      
       
        m
       
       
        +
       
       
        1
       
      
      
       m+1
      
     
    m+1 行，每行四个非负整数，
    
     
      
       
        p
       
       
        ,
       
       
        u
       
       
        ,
       
       
        v
       
       
        ,
       
       
        w
       
      
      
       p,u,v,w
      
     
    p,u,v,w 当 
    
     
      
       
        p
       
       
        =
       
       
        1
       
      
      
       p=1
      
     
    p=1 时，表示这个通信渠道为必选通信渠道；当 
    
     
      
       
        p
       
       
        =
       
       
        2
       
      
      
       p=2
      
     
    p=2 时，表示这个通信渠道为选择性通信渠道；
    
     
      
       
        u
       
       
        ,
       
       
        v
       
       
        ,
       
       
        w
       
      
      
       u,v,w
      
     
    u,v,w 表示本条信息描述的是 
    
     
      
       
        u
       
       
        ，
       
       
        v
       
      
      
       u，v
      
     
    u，v 管理员之间的通信渠道，
    
     
      
       
        u
       
      
      
       u
      
     
    u 可以收到 
    
     
      
       
        v
       
      
      
       v
      
     
    v 的信息，
    
     
      
       
        v
       
      
      
       v
      
     
    v 也可以收到 
    
     
      
       
        u
       
      
      
       u
      
     
    u的信息，
    
     
      
       
        w
       
      
      
       w
      
     
    w 表示费用。
 
输出 最小的通信费用 
样例输入 
 
 
5 6
 1 1 2 1
 1 2 3 1
 1 3 4 1
 1 4 1 1
 2 2 5 10
 2 2 5 5
 
 
样例输出 
 
 
9
 
 
数据范围限制 
对于 30%的数据，
    
     
      
       
        n
       
       
        ≤
       
       
        10
       
      
      
       nle10
      
     
    n≤10，
    
     
      
       
        m
       
       
        ≤
       
       
        100
       
      
      
       mle100
      
     
    m≤100
 对于 50%的数据, 
    
     
      
       
        n
       
       
        ≤
       
       
        200
       
      
      
       nle200
      
     
    n≤200，
    
     
      
       
        m
       
       
        ≤
       
       
        1000
       
      
      
       mle1000
      
     
    m≤1000
 对于 100%的数据，
    
     
      
       
        n
       
       
        ≤
       
       
        2000
       
      
      
       nle2000
      
     
    n≤2000，
    
     
      
       
        m
       
       
        ≤
       
       
        10000
       
      
      
       m le10000
      
     
    m≤10000
 
提示 

    
     
      
       
        1
       
       
        −
       
       
        2
       
       
        −
       
       
        3
       
       
        −
       
       
        4
       
       
        −
       
       
        1
       
      
      
       1-2-3-4-1
      
     
    1−2−3−4−1 存在四个必选渠道，形成一个环，互相可以到达。需要让所有管理员联通，需要联通 
    
     
      
       
        2
       
      
      
       2
      
     
    2 号和
    
     
      
       
        5
       
      
      
       5
      
     
    5 号管理员，选择费用为 
    
     
      
       
        5
       
      
      
       5
      
     
    5 的渠道，所以总的费用为
    
     
      
       
        9
       
      
      
       9
      
     
    9。
 注意：
    
     
      
       
        u
       
       
        ,
       
       
        v
       
      
      
       u,v
      
     
    u,v 之间可能存在多条通信渠道，你的程序应该累加所有 
    
     
      
       
        u
       
       
        ,
       
       
        v
       
      
      
       u,v
      
     
    u,v 之间的必选通行渠道
 
实现思路 
这题就先把为
    
     
      
       
        1
       
      
      
       1
      
     
    1必须加的加入并查集，然后，将其他的进行排序
 这题千万不要把数组开太大，也别太小，不然就RE，我就RE了，还是海笑帮我调的
 
Accepted Code 
#include
using namespace std;
#define N 10005
int qz,fa[N],n,t,ans,j;
struct no {
	int en,w,ne;
} a[N];
bool px(no a,no b) {
	return a.w
	return (fa[x]!=x)?(fa[x]=xz(fa[x])):x;
}
int main() {
	scanf("%d%d",&n,&t);
	for(int i=1; i<=n; i++) fa[i]=i;
	for(int i=1; i<=t; i++) {
		scanf("%d%d%d%d",&j,&a[i].ne,&a[i].en,&a[i].w);
		int x=xz(a[i].ne),y=xz(a[i].en);
		if(j==1) {//将1必须加的加入并查集，其他与上文的题差不多
			if(x
		int x=xz(a[i].ne),y=xz(a[i].en);
		if(x!=y) {
			ans+=a[i].w;
			if(x 
谢谢，大家观看