最小生成树

超、凢脫俗 2022-06-09 04:27 49阅读 0赞

邻接矩阵建图+prim朴素[算法][Link 1] 代码通过HDU1102

**\[cpp\]** [view plain][] [copy][view plain]

1.  \#include<iostream>
2.  **using****namespace** std; 
3.  **const****int** maxn=105,inf=1<<30; 
4.  **int** Map\[maxn\]\[maxn\],vis\[maxn\],d\[maxn\]; 
5.  **int** n,q,ans; 
6.  **int** prim() 
7.  \{ 
8.   fill(vis,vis+maxn,0);//初始化每个点都未被加入到答案集合中
9.   fill(d,d+maxn,inf);//初始化每个顶点到答案集合的最近距离
10.  d\[1\]=0;//将顶点1加入到答案集合中
11.  ans=0;//最小生成树权值
12. **while**(**true**) 
13.  \{ 
14. **int** v=-1;//记录下一个将要加入答案集合的顶点
15. **for**(**int** i=1;i<=n;i++)//贪心选取离答案集合距离最近的顶点
16. **if**(!vis\[i\]&&(v==-1||d\[i\]<d\[v\])) v=i; 
17. **if**(v==-1) **break**;//如果顶点都访问完了，那么v必然等于-1，则退出循环，算法结束
18.  vis\[v\]=1;//加入答案集合
19. **if**(d\[v\]==inf) **return** \-1;//存在孤立点，则不存在最小生成树
20.  ans+=d\[v\];//加上权值
21. **for**(**int** i=1;i<=n;i++)//更新未加入答案集合的那些顶点到答案集合的最小距离
22. **if**(!vis\[i\]) d\[i\]=min(d\[i\],Map\[v\]\[i\]); 
23.  \} 
24. **return** ans; 
25. \} 
26. **int** main() 
27. \{ 
28. **while**(cin>>n) 
29.  \{ 
30.  fill(&Map\[0\]\[0\],&Map\[maxn\]\[0\],inf); 
31. **for**(**int** i=1;i<=n;i++) 
32. **for**(**int** j=1;j<=n;j++) 
33.  cin>>Map\[i\]\[j\],Map\[j\]\[i\]=Map\[i\]\[j\]; 
34.  cin>>q; 
35. **while**(q--) 
36.  \{ 
37. **int** x,y; 
38.  cin>>x>>y; 
39.  Map\[x\]\[y\]=Map\[y\]\[x\]=0; 
40.  \} 
41.  cout<<prim()<<endl; 
42.  \} 
43. **return** 0; 
44. \}

邻接矩阵建图+prim堆优化算法，代码通过了HDU 1102

**\[cpp\]** [view plain][] [copy][view plain]

1.  \#include<iostream>
2.  \#include<queue>
3.  **using****namespace** std; 
4.  **const****int** maxn=105,inf=1<<30; 
5.  **int** Map\[maxn\]\[maxn\],vis\[maxn\],ans,n,d\[maxn\]; 
6.  **struct** node 
7.  \{ 
8.  **int** v,len;//v代表当前顶点，w代表v到答案集合的最小距离
9.  **friend****bool** operator <(node a,node b) 
10.  \{ 
11. **return** a.len>b.len; 
12.  \} 
13. \}; 
14. **int** prim() 
15. \{ 
16.  priority\_queue<node>q; 
17.  node t; 
18.  t.v=1;t.len=0; 
19.  q.push(t);//初始化顶点1到答案集合的距离为0，以保证第一次一定选入顶点1到答案集合中去
20.  ans=0; 
21.  fill(vis,vis+maxn,0); 
22.  fill(d,d+maxn,inf); 
23. **while**(q.size()) 
24.  \{ 
25.  t=q.top();q.pop();//取离答案集合距离最小的顶点
26. **if**(vis\[t.v\]) **continue**;//如果已经在答案集合中则进行下一次的循环
27.  vis\[t.v\]=1;//否则取顶点t.v加入到答案集合中
28.  ans+=t.len; 
29. **for**(**int** i=1;i<=n;i++)//更新未加入答案集合的顶点到答案集合 的距离
30.  \{ 
31. **if**(!vis\[i\]&&Map\[t.v\]\[i\]<d\[i\])//可以更新则入队
32.  \{ 
33.  node next; 
34.  next.v=i; 
35.  next.len=Map\[t.v\]\[i\]; 
36.  d\[i\]=Map\[t.v\]\[i\]; 
37.  q.push(next); 
38.  \} 
39.  \} 
40.  \} 
41. **return** ans; 
42. \} 
43. **int** main() 
44. \{ 
45.  cin.sync\_with\_stdio(0); 
46. **while**(cin>>n) 
47.  \{ 
48. **for**(**int** i=1;i<=n;i++) 
49. **for**(**int** j=1;j<=n;j++) 
50.  cin>>Map\[i\]\[j\]; 
51. **int** q; 
52.  cin>>q; 
53. **while**(q--) 
54.  \{ 
55. **int** x,y; 
56.  cin>>x>>y; 
57.  Map\[x\]\[y\]=Map\[y\]\[x\]=0;//x和y相连，那么它们之间的距离为0
58.  \} 
59.  cout<<prim()<<endl; 
60.  \} 
61. **return** 0; 
62. \}

邻接表建图+prim堆优化，代码通过了1301

**\[cpp\]** [view plain][] [copy][view plain]

1.  \#include<iostream>
2.  \#include<algorithm>
3.  \#include<vector>
4.  \#include<queue>
5.  \#include<cstdio>
6.  \#include<cstring>
7.  \#define LL long long
8.  **using****namespace** std; 
9.  **const****int** maxn=30,inf=1<<30; 
10. **using****namespace** std; 
11. **int** d\[maxn\],vis\[maxn\]; 
12. **struct** edge 
13. \{ 
14. **int** to,len; 
15.  edge(**int** to,**int** len):to(to),len(len)\{\} 
16. \}; 
17. **struct** node 
18. \{ 
19. **int** v,dist; 
20.  node(**int** x,**int** y):v(x),dist(y)\{\} 
21. **friend****bool** operator <(node a,node b) 
22.  \{ 
23. **return** a.dist>b.dist; 
24.  \} 
25. \}; 
26. vector<edge>G\[maxn\]; 
27. **int** prim() 
28. \{ 
29. **int** ans=0; 
30.  fill(vis,vis+maxn,0); 
31.  fill(d,d+maxn,inf); 
32.  priority\_queue<node>q; 
33.  q.push(node(0,0)); 
34. **while**(q.size()) 
35.  \{ 
36.  node t=q.top();q.pop(); 
37. **if**(vis\[t.v\]) **continue**; 
38.  vis\[t.v\]=1; 
39.  ans+=t.dist; 
40. **for**(**int** i=0;i<G\[t.v\].size();i++) 
41.  \{ 
42.  edge e=G\[t.v\]\[i\]; 
43. **if**(vis\[e.to\]) **continue**; 
44. **if**(e.len<d\[e.to\]) d\[e.to\]=e.len,q.push(node(e.to,e.len)); 
45.  \} 
46.  \} 
47. **return** ans; 
48. \} 
49. **int** main() 
50. \{ 
51. **int** n,w,op,from,to; 
52. **char** s,e; 
53. **while**(cin>>n,n) 
54.  \{ 
55. **for**(**int** i=0;i<=n;i++) G\[i\].clear(); 
56. **for**(**int** i=0;i<n-1;i++) 
57.  \{ 
58.  cin>>s>>op; 
59.  from=s-'A'; 
60. **for**(**int** j=0;j<op;j++) 
61.  \{ 
62.  cin>>e>>w; 
63.  to=e-'A'; 
64.  G\[from\].push\_back(edge(to,w)); 
65.  G\[to\].push\_back(edge(from,w)); 
66.  \} 
67.  \} 
68.  cout<<prim()<<endl; 
69.  \} 
70. **return** 0; 
71. \}

kruskal模板 通过HDU1863，

**\[cpp\]** [view plain][] [copy][view plain]

1.  //prim+堆优化，以九度OJ 1347为例
2.  //http://ac.jobdu.com/problem.php?pid=1347
3.  \#include<cstdio>
4.  \#include<algorithm>
5.  **const****int** L=100005; 
6.  **struct** node\{ **int** s,y,w;\}edge\[L\]; 
7.  **int** Fa\[L\],n,m; 
8.  **void** init()//初始化并查集
9.  \{ 
10. **for**(**int** i=0;i<=n;i++) Fa\[i\]=i; 
11. \} 
12. **int** Find(**int** x)//查询属于哪个集合
13. \{ 
14. **if**(Fa\[x\]==x) **return** x; 
15. **else****return** Fa\[x\]=Find(Fa\[x\]); 
16. \} 
17. **void** unite(**int** x,**int** y)//合并x,y两个元素
18. \{ 
19.  x=Find(x);y=Find(y); 
20. **if**(x==y) **return** ; 
21.  Fa\[y\]=x; 
22. \} 
23. **bool** same(**int** x,**int** y)//【判断是否属于同个集合
24. \{ 
25. **return** Find(x)==Find(y); 
26. \} 
27. **bool** cmp(node a,node b) 
28. \{ 
29. **return** a.w<b.w; 
30. \} 
31. **int** main() 
32. \{ 
33. **while**(~scanf("%d%d",&m,&n)&&m) 
34.  \{ 
35.  init(); 
36. **for**(**int** i=0;i<m;i++) 
37.  scanf("%d%d%d",&edge\[i\].s,&edge\[i\].y,&edge\[i\].w); 
38.  std::sort(edge,edge+m,cmp); 
39. **int** sum=0,cnt=0; 
40. **for**(**int** i=0;i<m;i++) 
41.  \{ 
42. **if**(cnt==n-1) **break**; 
43. **if**(!same(edge\[i\].s,edge\[i\].y)) 
44.  \{ 
45.  unite(edge\[i\].s,edge\[i\].y); 
46.  sum+=edge\[i\].w; 
47.  cnt++; 
48.  \} 
49.  \} 
50. **if**(cnt!=n-1) printf("?\\n"); 
51. **else** printf("%d\\n",sum); 
52.  \} 
53. **return** 0; 
54. \}

转载自：http://blog.csdn.net/u013615904/article/details/48003679

[Link 1]: http://lib.csdn.net/base/datastructure
[view plain]: http://blog.csdn.net/u013615904/article/details/48003679#