目录
模板例题
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()
