最小生成树

写在前面：我是一只蒟蒻。

好的，今天我们来讲一讲“最小生成树”。

首先，我们来看看什么是最小生成树，

定义：

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。（摘自百度百科）

定理：任意一棵最小生成树一定包含无向图中权值最小的边。

证明：

反证法。假设无向图G=（V,E）存在一棵最小生成树不包含权值最小的边。设边e（x,y,z）是无向图中权值最小的边。把e加入到树中，e会和树上的x，y构成一个环，且e比环上任意一条边要小，所以用e来替换环上的任意一条边，就会得到比原树更小的生成树，与结论矛盾，所以此结论成立。

对于这样的一个问题，我们有什么算法来解决呢？

下面，我就给大家来介绍一下解决这类问题的两种算法：

kruskal算法

首先，我们从先从定义来看，要找最小生成树，就要先找边权最短，所以我们就可以先排序（以边权值从小到大），然后再寻找两边能否使图连通，如果可以就加入这棵树，这时我们就需要使用并查集来维护。

下面是伪代码流程：

1、首先我们先用并查集将每个点的祖先初始化

2、排序

3、扫描每条边，判断是否是联通两点的最短边

下面是图形的演示

   

 

 

代码：

#include<bits/stdc++.h>
#define N 200007
#define maxn 5007
using namespace std;
struct edge{
    int x,w,y;
}e[N*2];
int head[maxn],tot,num,ans,fa[maxn],n,m;
bool cmp(edge a,edge b){
    return a.w<b.w;
}
int find(int x){
    if(x==fa[x])return x;
    fa[x]=find(fa[x]);
    return fa[x];
}
void kruskal(){
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        int x=e[i].x,y=e[i].y;
        if(find(x)==find(y))continue;
        fa[find(x)]=find(y);
        ans+=e[i].w;
        num++;
        if(num==n-1)break;
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
    }
    sort(e+1,e+1+m,cmp);
    kruskal();
    printf("%d
",ans);
    return 0;
}

 看完模板代码，我们来看一道例板子题：洛谷P1546

题目：

题目背景

农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。

题目描述

约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。

你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000

输入输出格式

输入格式：

第一行： 农场的个数，N（3<=N<=100）。

第二行..结尾: 后来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上，他们是N行，每行由N个用空格分隔的数组成，实际上，他们限制在80个字符，因此，某些行会紧接着另一些行。当然，对角线将会是0，因为不会有线路从第i个农场到它本身。

输出格式：

只有一个输出，其中包含连接到每个农场的光纤的最小长度。

输入输出样例

输入样例#1：

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

输出样例#1：

28

这道题，我们读完题就可以十分十分简单的看出这道题是道图论（废话，不说我也能看出来 ）。。。。。。

再一看，我们又看到我们就要建树，为了满足题意的条件，我们就要找最小生成树。

nice！下一道。（本题AC代码放置博客最后）

 洛谷P2330

题目：

题目描述

城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市C的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：

1．改造的那些道路能够把所有的交叉路口直接或间接的连通起来。 2．在满足要求1的情况下，改造的道路尽量少。 3．在满足要求1、2的情况下，改造的那些道路中分值最大的道路分值尽量小。

任务：作为市规划局的你，应当作出最佳的决策，选择那些道路应当被修建。

输入输出格式

输入格式：

第一行有两个整数n,m表示城市有n个交叉路口，m条道路。

接下来m行是对每条道路的描述，u, v, c表示交叉路口u和v之间有道路相连，分值为c。(1≤n≤300，1≤c≤10000，1≤m≤100000)

输出格式：

两个整数s, max，表示你选出了几条道路，分值最大的那条道路的分值是多少。

输入输出样例

输入样例#1：

4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8

输出样例#1：

3 6

这道题在上一道题上又多了一个新的概念“瓶颈生成树”，什么是瓶颈生成树，很简单，我们来看一下它的定义：
无向图G的一颗瓶颈生成树是这样的一颗生成树T，它最大的边权值在G的所有生成树中是最小的。瓶颈生成树的值为T中最大权值边的。

一个结论：无向图的最小生成树一定是瓶颈生成树，但瓶颈生成树不一定是最小生成树。

其正确性就不在此证明了，这道题就是一颗瓶颈生成树，我们只需要在找最小生成树时统计一下最小边加的边数，最后输出就可以了。

---

6月26日更新

非常抱歉，当时在写完这部分之后就忘了还缺内容，今天在做到最小生成树的题的时候，才想起来。

补得代码：

#include<bits/stdc++.h>
using namespace std;
#define maxn 200002
struct edge{
    int x,y,w;
}e[maxn*2];
int head[maxn],tot,n,ans,p=1,fa[maxn];
void add(int a,int b,int c){
    e[++tot].w=c;
    e[tot].x=a;
    e[tot].y=b;
}
int cmp(edge a,edge b){
    return a.w<b.w;
}
int find(int x){
    if(fa[x]==x)return x;
    fa[x]=find(fa[x]);
    return fa[x];
}
void kruskal(){
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=tot;i++){
        int x=e[i].x,y=e[i].y;
        if(find(x)==find(y))continue;
        fa[find(x)]=find(y);
        ans+=e[i].w;
        p++;
        if(p==n)break;
    }
}


int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int a;
            scanf("%d",&a);
            if(i<j){
                add(i,j,a);
                add(j,i,a);
            }
        }
    }
    sort(e+1,e+1+tot,cmp);
    kruskal();
    printf("%d
",ans);


    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define maxn 100007
#define N 308
struct edge{
    int x,y,w;
}e[maxn*2];
int head[N],tot,ans,maxx=0,fa[N],n,m;
void add(int a,int b,int c){
    e[++tot].x=a;
    e[tot].w=c;
    e[tot].y=b;
}
int cmp(edge a,edge b){
    return a.w<b.w;
}
int find(int x){
    if(fa[x]==x)return fa[x];
    fa[x]=find(fa[x]);
    return fa[x];
}
void kruskal(){
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=tot;i++){
        int x=find(e[i].x);
        int y=find(e[i].y);
        if(x==y)continue;
        fa[x]=y;
        ans++;
        maxx=max(e[i].w,maxx);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    sort(e+1,e+1+tot,cmp);
    kruskal();
    printf("%d %d
",ans,maxx);
    return 0;
}

下面进入主题：

好久之前我们介绍了kruskal算法求最小生成树

 今天，我们来看一看

Prim算法

Prim算法与kruskal算法的核心思想是一样的，但是思路和操作的方式有些不同，Prim总是维护最小生成树的一部分。在最开始，其只是确定最小生成树的一个点。

操作流程:

① 先建立一个只有一个结点的树，这个结点可以是原图中任
意的一个结点。
② 使用一条边扩展这个树，要求这条边一个顶点在树中另一
个顶点不在树中，并且这条边的权值要求最小。
③ 重复步骤②直到所有顶点都在树中。

模板：

#include<bits/stdc++.h>
using namespace std;
#define N 5010
int a[N][N],d[N],n,m,ans;
bool vis[N];//指示该点是否在最小生成树中
void prim(){
    memset(d,0x3f3f3f3f,sizeof(d));
    memset(vis,0,sizeof(vis));
    d[1]=0;//初始点
    for(int i=1;i<n;i++){
        int x=0;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&d[j]<d[x])x=j;
        }
        vis[x]=1;//加入树中
        for(int j=1;j<=n;j++){
            if(!vis[j])d[j]=min(d[j],a[x][j]);
        }
    }
}


int main(){
    scanf("%d%d",&n,&m);
    memset(a,0x3f3f3f3f,sizeof(a));
    for(int i=1;i<=n;i++){
        a[i][i]=0;
    }
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        a[y][x]=a[x][y]=min(a[x][y],z);
    }
    prim();
    for(int i=2;i<=n;i++)ans+=d[i];
    printf("%d",ans);



    return 0;
}

Prim 主要用于稠密图，完全图。

下面给大家推荐一道题

洛谷P1265

代码（前面的kruskal。。。是错的）：

/*#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y;
    double w;
}e[10007];
double calc(int x,int y,int xx,int yy){
    return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));//求两点距离
}
int head[5007],fa[5007],n,cnt,dis[5007][5007];
struct NODE{
    int x,y;
}a[5007];
int find(int x){
    if(fa[x]==x)return fa[x];
    fa[x]=find(fa[x]);
    return fa[x];
}
bool cmp(node a,node b){
    return a.w<b.w;
}

void add(int a,int b,double c){
    e[++cnt].x=a;
    e[cnt].y=b;
    e[cnt].w=c;
}

// double 


int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        // int a,b;
        scanf("%d%d",&a[i].x,&a[i].y);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j)continue;
            add(i,j,calc(a[i].x,a[i].y,a[j].x,a[j].y));
            fa[i]=i;
        }
    }
    double ans=0;
    sort(e+1,e+1+cnt,cmp);
    for(int i=1;i<=cnt;i++){
        int x=e[i].x;
        int y=e[i].y;
        int f1=find(x);
        int f2=find(y);
        if(f1==f2){
            continue;
        }
        fa[f1]=f2;
        ans+=e[i].w;
    }
    printf("%0.2f",ans);
    return 0;
}*///kruskal
//prim算法
#include<bits/stdc++.h>
using namespace std;
#define N 5007
#define INF 100000000
template <typename type>
void scan(type &x){
    type f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}
struct node{
    int x,y;
}a[N];
double dis[N],ans;
bool vis[N];//记录数组
int n;
double calc(int x,int y,int xx,int yy){
    return sqrt((double)(x-xx)*(x-xx)+(double)(y-yy)*(y-yy));//求两点距离
}
int main(){
    scan(n);
    for(int i=1;i<=n;i++){
        scan(a[i].x);
        scan(a[i].y);
        dis[i]=INF;
    }
    dis[1]=0;
    int k;
    for(int i=1;i<=n;i++){
        double minn=INF;
        for(int j=1;j<=n;j++){
         if(!vis[j]&&dis[j]<minn){
                minn=dis[j];
                k=j;//取最优点
            }
        }
        ans+=minn;vis[k]=1;//最优点加入树中
        for(int j=1;j<=n;j++){
            double d=calc(a[k].x,a[k].y,a[j].x,a[j].y);
            if(dis[j]>d) dis[j]=d;
         }
    }
    printf("%.2lf",ans);
    return 0;
}