最小生成树

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

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

[cpp] view plain copy

  1. #include
  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

  1. #include
  2. #include
  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_queueq;
  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

  1. #include
  2. #include
  3. #include
  4. #include
  5. #include
  6. #include
  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. vectorG[maxn];
  27. int prim()
  28. {
  29. int ans=0;
  30. fill(vis,vis+maxn,0);
  31. fill(d,d+maxn,inf);
  32. priority_queueq;
  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

  1. //prim+堆优化，以九度OJ 1347为例
  2. //http://ac.jobdu.com/problem.php?pid=1347
  3. #include
  4. #include
  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

发表评论

表情：
评论列表 （有 0 条评论，184人围观）

还没有评论，来说两句吧...

相关阅读

    相关 最小生成树

    最小生成树定义： 在一给定的无向图 G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即![(u, v)\\in E][u_ v_in E]），而

    末蓝、末蓝、/ 0 赞/ 316 阅读

    相关 最小生成树

    一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。 最小生成树在n个顶点的情形下，有n-1条边。生成树是对连

    忘是亡心i忘是亡心i/ 0 赞/ 334 阅读

    相关 最小生成树

    有n个城市，m条道路，现在输入n到m的道路的长度，用最少的边将图连接，输出让图连接的最小值 这道题我研究了好长时间才把答案看明白，现在给大家分享一下 具体代码如下

    爱被打了一巴掌爱被打了一巴掌/ 0 赞/ 276 阅读

    相关 最小生成树

    问题提出： 要在n个城市间建立通信联络网。顶点：表示城市，权：城市间通信线路的花费代价。希望此通信网花费代价最小。 问题分析： 答案只能从生成树中找，因为要做到任何

    雨点打透心脏的1/2处雨点打透心脏的1/2处/ 0 赞/ 394 阅读

    相关 最小生成树

    kruskal算法基本思路：先对边按权重从小到大排序，先选取权重最小的一条边，如果该边的两个节点均为不同的分量，则加入到最小生成树，否则计算下一条边，直到遍历完所有的边。 p

    ゝ一纸荒年。ゝ一纸荒年。/ 0 赞/ 370 阅读

    相关 最小生成树

    最小生成树 什么是最小生成树 给定一张无向带权图G=(V,E,W),从中挑选出|V|-1条边，使得V中任意两点都有直接或者间接的路径 显然，最后得到的子

    浅浅的花香味﹌浅浅的花香味﹌/ 0 赞/ 432 阅读