目录

模板例题

输入描述

输出描述

输入输出样例

运行限制

prim算法

c

python

Kruskal算法

c++

python

---

模板例题

L 城一共有 N 个小区。

小明是城市建设的规划者，他计划在城市修 M 条路，每修建一条路都要支付工人们相应的工钱（需要支付的工钱 = 路的长度）。

然而小明所拿到的经费并不够支付修建 M 条路的工钱，于是迫于无奈，他只能将计划改变为修建若干条路，使得 N 个小区之间两两联通。

小明希望尽量剩下更多的经费投入到别的项目中，因此请你通过程序帮他计算出完成计划所需的最低开销。

输入描述

输入第一行包含三个正整数 N,M。

第 2到 M + 1 行每行包含三个正整数 u,v,w，表示 u↔v 之间存在一条距离为 w 的路。

1≤N≤10^5，0≤m≤3×10^5，1≤ui​,vi​≤N，0≤wi​≤10^9。

输出描述

输出占一行，包含一个整数，表示完成计划所需的最低开销。

若无法完成计划，则输出 -1。

输入输出样例

示例 1

输入

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

输出

8

运行限制

• 最大运行时间：3s
• 最大运行内存: 256M

prim算法

c++

pii第一个值是边的权重，第二个值是这条边上的一个点的编号

#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N=100010;
const int INF=0x3f3f3f;
bool vis[N];  // =ture: 表示点i已经在MST中
int dis[N];
typedef pair<int,int> pii;
vector<pii> g[N];
priority_queue<pair<int,int>,vector<pii>,greater<pii> > q;  //优先队列
void prim(int s){
    memset(dis,INF,sizeof(dis));
    q.push({0,s});   //从s点开始处理队列
    dis[s]=0;
    long long ans=0; // 答案可能很大，要开long long
    while(!q.empty())    {
        int u=q.top().second;   //pop出距集合最近的点u
        q.pop();
        if(vis[u]) continue;    //丢弃已经在MST中的点，有判圈的作用
        vis[u]=1;
        ans+=dis[u];
        for(int i=0;i<g[u].size();i++){ //检查点u的所有邻居
            pii v=g[u][i];          //一个邻居
            if(!vis[v.second])
                if(v.first<dis[v.second]){
                    dis[v.second]=v.first;
                    q.push(pii(dis[v.second],v.second));//扩展新的邻居，放进优先队列
                }
        }
    }
    for(int i=1;i<=n;i++)
        if(!vis[i]){
            cout<<"-1"<<endl;
            return ;
        }
    cout<<ans<<endl;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        g[x].push_back({z,y});  //双向边
        g[y].push_back({z,x});
    }
    prim(1);
    return 0;
}

python

在python代码中，通过head列表实现对结点i的邻居结点的访问

from heapq import heappush, heappop
 
def add(u, v, w):
    global k
    edges[k][0] = v
    edges[k][1] = w
    edges[k][2] = head[u]
    head[u] = k
    k += 1
 
def prime():
    global cnt, ans
    dis = [float('inf') for _ in range(n + 1)]
    dis[1] = 0
    q = []
    vis = [False for _ in range(n + 1)]   # =ture: 表示点i已经在MST中
    heappush(q, (0, 1))  #从s点开始处理队列
 
    while q and cnt < n:
        w, u = heappop(q)    #pop出距集合最近的点u
        if not vis[u]:
            vis[u] = True
            ans += w
            i = head[u]
            cnt += 1
            while i:           #检查点u的所有邻居
                v = edges[i][0]
                if dis[v] > edges[i][1]:
                    dis[v] = edges[i][1]
                    heappush(q, [dis[v], v])#扩展新的邻居，放进优先队列
                i = edges[i][2]
 
n, m = map(int,input().split())
edges = [[0, 0, 0] for i in range(2 * m + 1)]
head = [0 for i in range(n + 1)]
k = 1
ans, cnt = 0, 0
for i in range(m):
    u, v, w = map(int,input().split())
    add(u, v, w)         #双向边
    add(v, u, w)
prime()
if cnt != n:    print('-1')
else:           print(ans)

Kruskal算法

c++

在c++代码中通过已经覆盖的点的数量判断是否可以生成最小树

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+1,M = 3e5+1;
int n,m,cnt;
long long ans;
int s[N];//并查集
struct Edge{ int from,to,dis;}edge[M]; //用最简单且最省空间的结构体数组存边
bool cmp(Edge a,Edge b){  //从小到大排序
    return (a.dis<b.dis);
}
int find(int x)  { //查询并查集，返回x的根
    if(x!=s[x]) s[x]=find(s[x]);//路径压缩
    return s[x];
}
void union_set(int x,int y)   {   //合并
    s[find(y)]=find(x);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i)
        cin>>edge[i].from>>edge[i].to>>edge[i].dis;
    for(int i=1;i<=n;++i) //并查集初始化
        s[i]=i;
    sort(edge+1,edge+1+m,cmp);//对边做排序
    for(int i=1;i<=m;++i){   //贪心：逐一加入每个边
        if(find(edge[i].from)!=find(edge[i].to)){ //边的端点属于同一个集吗
            ans+=edge[i].dis; //计算MST
            union_set(edge[i].from,edge[i].to);//合并
            ++cnt;                 //小 统计MST中的点数
        }
        if(cnt==n-1) break;
    }
    if(cnt!=n-1)     cout<<"-1";
    else         cout<<ans;
    return 0;
}

python

在python代码中判断有无最小生成树是通过并查集的find函数实现的。

edges = []
added_edges = []
s = []                       #并查集
def find(x):                 #查询并查集，返回x的根
    if s[x] == x:  return x
    s[x] = find(s[x])        #路径压缩
    return s[x]
 
def main():
    n,m = map(int,input().split())    
    for i in range(1, m + 1):
        x, y, z = map(int,input().split())
        edges.append((x, y, z))         #读边
#下面是kruskal
    edges.sort(key=lambda tup: tup[2])   #对边做排序
    for i in range(n + 1):  s.append(i)  #并查集初始化
    for i in range(m):
        x, y = edges[i][0], edges[i][1]
        e1, e2 = find(x), find(y)
        if e1 == e2:         #属于同一个集：产生了圈，丢弃
            continue
        else:
            added_edges.append(i)
            s[s[x]] =s[y]        #合并
    find(1)
    for i in range(2, n + 1):
        if find(i) != s[i - 1]:     
            print("-1")
            return
    ans = 0
    for i in added_edges:
        ans += edges[i][2]
    print(ans)
    return
main()