模板例题
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
输入
1. 5 6 2. 1 2 2 3. 1 3 7 4. 1 4 6 5. 2 3 1 6. 3 4 3 7. 3 5 2
输出
8
运行限制
- 最大运行时间：3s
- 最大运行内存: 256M
prim算法
c++
pii第一个值是边的权重，第二个值是这条边上的一个点的编号
1. #include <bits/stdc++.h> 2. using namespace std; 3. int n,m; 4. const int N=100010; 5. const int INF=0x3f3f3f; 6. bool vis[N]; // =ture: 表示点i已经在MST中 7. int dis[N]; 8. typedef pair<int,int> pii; 9. vector<pii> g[N]; 10. priority_queue<pair<int,int>,vector<pii>,greater<pii> > q; //优先队列 11. void prim(int s){ 12. memset(dis,INF,sizeof(dis)); 13. q.push({0,s}); //从s点开始处理队列 14. dis[s]=0; 15. long long ans=0; // 答案可能很大，要开long long 16. while(!q.empty()) { 17. int u=q.top().second; //pop出距集合最近的点u 18. q.pop(); 19. if(vis[u]) continue; //丢弃已经在MST中的点，有判圈的作用 20. vis[u]=1; 21. ans+=dis[u]; 22. for(int i=0;i<g[u].size();i++){ //检查点u的所有邻居 23. pii v=g[u][i]; //一个邻居 24. if(!vis[v.second]) 25. if(v.first<dis[v.second]){ 26. dis[v.second]=v.first; 27. q.push(pii(dis[v.second],v.second));//扩展新的邻居，放进优先队列 28. } 29. } 30. } 31. for(int i=1;i<=n;i++) 32. if(!vis[i]){ 33. cout<<"-1"<<endl; 34. return ; 35. } 36. cout<<ans<<endl; 37. } 38. int main(){ 39. cin>>n>>m; 40. for(int i=0;i<m;i++){ 41. int x,y,z; 42. scanf("%d%d%d",&x,&y,&z); 43. g[x].push_back({z,y}); //双向边 44. g[y].push_back({z,x}); 45. } 46. prim(1); 47. return 0; 48. }
python
在python代码中，通过head列表实现对结点i的邻居结点的访问
1. from heapq import heappush, heappop 2. 3. def add(u, v, w): 4. global k 5. edges[k][0] = v 6. edges[k][1] = w 7. edges[k][2] = head[u] 8. head[u] = k 9. k += 1 10. 11. def prime(): 12. global cnt, ans 13. dis = [float('inf') for _ in range(n + 1)] 14. dis[1] = 0 15. q = [] 16. vis = [False for _ in range(n + 1)] # =ture: 表示点i已经在MST中 17. heappush(q, (0, 1)) #从s点开始处理队列 18. 19. while q and cnt < n: 20. w, u = heappop(q) #pop出距集合最近的点u 21. if not vis[u]: 22. vis[u] = True 23. ans += w 24. i = head[u] 25. cnt += 1 26. while i: #检查点u的所有邻居 27. v = edges[i][0] 28. if dis[v] > edges[i][1]: 29. dis[v] = edges[i][1] 30. heappush(q, [dis[v], v])#扩展新的邻居，放进优先队列 31. i = edges[i][2] 32. 33. n, m = map(int,input().split()) 34. edges = [[0, 0, 0] for i in range(2 * m + 1)] 35. head = [0 for i in range(n + 1)] 36. k = 1 37. ans, cnt = 0, 0 38. for i in range(m): 39. u, v, w = map(int,input().split()) 40. add(u, v, w) #双向边 41. add(v, u, w) 42. prime() 43. if cnt != n: print('-1') 44. else: print(ans)
Kruskal算法
c++
在c++代码中通过已经覆盖的点的数量判断是否可以生成最小树
1. #include<bits/stdc++.h> 2. using namespace std; 3. const int N = 1e5+1,M = 3e5+1; 4. int n,m,cnt; 5. long long ans; 6. int s[N];//并查集 7. struct Edge{ int from,to,dis;}edge[M]; //用最简单且最省空间的结构体数组存边 8. bool cmp(Edge a,Edge b){ //从小到大排序 9. return (a.dis<b.dis); 10. } 11. int find(int x) { //查询并查集，返回x的根 12. if(x!=s[x]) s[x]=find(s[x]);//路径压缩 13. return s[x]; 14. } 15. void union_set(int x,int y) { //合并 16. s[find(y)]=find(x); 17. } 18. int main(){ 19. cin>>n>>m; 20. for(int i=1;i<=m;++i) 21. cin>>edge[i].from>>edge[i].to>>edge[i].dis; 22. for(int i=1;i<=n;++i) //并查集初始化 23. s[i]=i; 24. sort(edge+1,edge+1+m,cmp);//对边做排序 25. for(int i=1;i<=m;++i){ //贪心：逐一加入每个边 26. if(find(edge[i].from)!=find(edge[i].to)){ //边的端点属于同一个集吗 27. ans+=edge[i].dis; //计算MST 28. union_set(edge[i].from,edge[i].to);//合并 29. ++cnt; //小 统计MST中的点数 30. } 31. if(cnt==n-1) break; 32. } 33. if(cnt!=n-1) cout<<"-1"; 34. else cout<<ans; 35. return 0; 36. }
python
在python代码中判断有无最小生成树是通过并查集的find函数实现的。
1. edges = [] 2. added_edges = [] 3. s = [] #并查集 4. def find(x): #查询并查集，返回x的根 5. if s[x] == x: return x 6. s[x] = find(s[x]) #路径压缩 7. return s[x] 8. 9. def main(): 10. n,m = map(int,input().split()) 11. for i in range(1, m + 1): 12. x, y, z = map(int,input().split()) 13. edges.append((x, y, z)) #读边 14. #下面是kruskal 15. edges.sort(key=lambda tup: tup[2]) #对边做排序 16. for i in range(n + 1): s.append(i) #并查集初始化 17. for i in range(m): 18. x, y = edges[i][0], edges[i][1] 19. e1, e2 = find(x), find(y) 20. if e1 == e2: #属于同一个集：产生了圈，丢弃 21. continue 22. else: 23. added_edges.append(i) 24. s[s[x]] =s[y] #合并 25. find(1) 26. for i in range(2, n + 1): 27. if find(i) != s[i - 1]: 28. print("-1") 29. return 30. ans = 0 31. for i in added_edges: 32. ans += edges[i][2] 33. print(ans) 34. return 35. main()
