最小生成树模板（prim算法和kruskal算法）

题目描述
随着如今社会的不断变化，交通问题也变得越来越重要，所以市长决定建设一些公路来方便各个城市之间的贸易和交易。

虽然市长的想法很好，但是他也遇到了一般人也经常头疼的问题，那就是手头的经费有限……在规划过程中，设计师们已经预算出部分城市之间建设公路的经费需求。

现在市长想知道，它能不能将他的m个城市在有限的经费内实现公路交通。

如果可以的话，输出Yes，否则输出No（两个城市不一定要直接的公路相连，间接公路到达也可以。

）

输入描述:
测试输入包含多条测试数据
每个测试数据的第1行分别给出可用的经费c(<1000000)，道路数目n(n<10000)，以及城市数目m(<100)。

接下来的n行给出建立公路的成本信息，每行给出三个整数，分别是相连的两个城市v1、v2(0

输出描述:
对每个测试用例，输出Yes或No。

链接：道路建设
来源：牛客网

示例
输入

20 10 5
1 2 6
1 3 3
1 4 4
1 5 5
2 3 7
2 4 7
2 5 8
3 4 6
3 5 9
4 5 2

输出

Yes

备注:
两个城市之间可能存在多条线路

最小生成树动态效果演示：Prim算法与Kruskal算法

Prim算法实现（与最短路Dijkstra非常相似，区别在于dist[j]意义不同）

算法思想：将所有点划分为两个集合，S为所选顶点集合，V-S为未选顶点集合。

每次从V-S集合中寻找某个点到达S集合的最短距离dist[j]，并将该点加入集合S，同时需要注意更新V-S集合中点j的最短距离，判断当前dist[j]与新加入集合S的点cur到达点j的距离mp[cur][j]的大小。

核心步骤：初始化–>寻找最短距离dist[j]–>将新的点cur加入集合S–>累加该边的权值–>更新最短距离

#include 

using namespace std;

const int maxx=101;  //顶点数量的最大值
const int inf=0x3f3f3f3f;
int mp[maxx][maxx];  //存边的权值信息
int dist[maxx];  //表示未选顶点到达已选顶点集合的最短距离
int flag[maxx];  //标记某个点是否被选择
int n,m,u,v,w;
long long sum=0;  //对最小生成树边的权值累加

int prim(int u){ //设初始选择的点为u
    for(int i=1;i<=n;i++){
        dist[i]=mp[u][i];  //初始化最短距离dist[i]为起始点u与该点的距离
        flag[i]=0;  //设初始状态未选择任何点
    }
    flag[u]=1; //将顶点u加入集合S
    dist[u]=0;  //u距离起始点u距离为0
    for(int i=1;i<=n;i++){
        int t=inf,cur=-1; //t为中间变量，用于寻找最短距离dist[j];cur为新加入集合S的点
        for(int j=1;j<=n;j++){  //从未选顶点集合V-S中寻找距离已选顶点集合S最近的点
            if(!flag[j]&&dist[j]<t){
                t=dist[j];  //找到最短距离的边
                cur=j;  //找到最近的点标记为cur
            }
        }
        if(dist[cur]>=inf) return inf;  //若不存在最小生成树，则提前结束
        flag[cur]=1; //将新的点cur加入集合S
        sum+=dist[cur];
        for(int j=1;j<=n;j++){ //更新点j到达集合S的最短距离
            if(!flag[j])  dist[j]=min(dist[j],mp[cur][j]);
        }
    }
    return sum;
}

int main()
{
    int c; //道路经费
    while(cin>>c>>m>>n){ //m边（道路）的数量，n点（城市）的数量
        memset(mp,inf,sizeof(mp));  //初始状态未选择任何点，即没有边记为无穷大
        memset(dist,inf,sizeof(dist)); //初始状态距离集合S最短距离均为无穷大
        for(int i=1;i<=m;i++){ //输入各条边的权值信息
            cin>>u>>v>>w;
            mp[u][v]=min(mp[u][v],w);
          //mp[v][u]=min(mp[v][u],w); //无向图中u->v与v->u距离相等
        }
        int cost=prim(1); //最小生成树中最小的权值和
        if(cost>=inf) cout<<"No"<<endl; //不存在最小生成树
        else if(cost<=c) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

Kruskal算法实现（需要用到并查集判断两个点是否属于同一集合）
并查集详解

算法思想：按边的权值大小进行排序，每次选择权值最小的边加入集合；初始状态每个点都是独立的集合，由于不能构成环，加入集合的边需要满足边的两个端点u和v必须属于不同集合，需要使用并查集判断两个点的根结点是否相同，若相同证明两个点属于同一个集合，否则即可将该边加入集合中。

#include 

using namespace std;

const int maxx=1e6;  //边的数量的最大取值
int pre[maxx]; //记录每个点的前驱结点
struct node  //用结构体存每条边的权值信息
{
    int u,v,w;
} mp[maxx];
bool cmp(node a,node b) //按边权值升序排列
{
    return a.w<b.w;
}
int get(int x) //寻找点x的根结点
{
    while(pre[x]!=x)
        x=pre[x];
    return x;
    //return pre[x]==x?x:get(pre[x]);  //与get()函数体功能相同
}
int c,n,m;

int kruskal()
{
    long long sum=0;  //计算边的权值之和
    for(int i=1; i<=n; i++)
    {
        pre[i]=i;  //初始化每个点的前驱结点为自身，开始时每个点都是一个独立集合
    }
    sort(mp+1,mp+m+1,cmp);  //按边的权值大下从小到大排序，每次先取最小边加入集合
    for(int j=1; j<=m; j++)  //遍历m条边
    {
        int x=get(mp[j].u); //获取每条边两端顶点的根结点
        int y=get(mp[j].v);
        if(x==y) continue;  //若两端顶点根结点相同，证明两点在同一集合中，会形成环
        else pre[y]=x;  //否则将后继结点y加入前驱结点x集合中
        sum+=mp[j].w;  //将加入的边u->v权值进行累加
    }
    return sum;  //返回最小生成树权值之和
}
int main()
{
    while(cin>>c>>m>>n)  //进行多组测试数据输入
    {
        for(int i=1; i<=m; i++)  //输入m条边权值信息存到mp结构体数组中
        {
            cin>>mp[i].u>>mp[i].v>>mp[i].w;
        }
        if(kruskal()<=c)
            cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

希望对你有所帮助！