怒江傈僳族自治州网站建设_网站建设公司_在线商城_seo优化

【题目描述】

【输入】

【输出】

【输入样例】

5 8 1 2 2 2 5 9 5 4 7 4 1 10 1 3 12 4 3 6 5 3 3 2 3 8

【输出样例】

1 2 2 3 3 4 3 5

1. 算法一：Kruskal 算法 (克鲁斯卡尔)

核心思想：贪心策略，以边为核心。

1. 将所有边按照权值从小到大排序。

2. 依次枚举每一条边，利用并查集判断该边的两个端点是否已经连通。

3. 如果不连通，就选中这条边，并合并集合；如果已连通，则跳过。

适用场景：稀疏图（点多边少），竞赛中最常用的写法，代码短且不易错。

复杂度：O(M log M)

//第一种方法kruskal #include <iostream> #include <algorithm>//对应sort函数 using namespace std; int n,e; int fa[110];//存储每个节点所在集合的老大 struct edge{ int u;//边起点 int v;//边终点 int w;//边权 //重载运算符，按照边权从小到大排序 friend bool operator <(edge a,edge b){ return a.w<b.w; } }ed[20010];//边集数组 edge mst[20010];//记录最小生成树的边 long long sum;//记录最短工程总造价 int cnt;//记录连起来的边数 //并查集查询+路径压缩 int find(int a){ if(fa[a]==a) return a;//如果已经是根结点就返回 //否则就递归找根节点并将根结点变成路径上每个节点的祖先节点 return fa[a]=find(fa[a]); } //并查集合并 void uni(int x,int y){ int fax=find(x);//找到x的集合中老大 int fay=find(y);//找到y的集合中老大 //如果老大是同一个无事发生，否则就让x的祖先变成y的祖先的祖先(合并为一个集合) if(fax!=fay){ fa[fay]=fax; } } int main(){ cin>>n>>e;//城市数 边数 for(int i=1;i<=e;i++) cin>>ed[i].u>>ed[i].v>>ed[i].w; //将边集数组按边权从小到大排序 注意这里是ed+e+1不是ed+n+1 sort(ed+1,ed+e+1); for(int i=1;i<=n;i++) fa[i]=i;//初始化每个城市自成集合 for(int i=1;i<=e;i++){//遍历所有边（按照边权从小到大） int a=ed[i].u; int b=ed[i].v; if(find(a)!=find(b)){//如果这条边的起点和终点不在一个集合 cnt++;//连起来的边数+1 mst[cnt].u=a; mst[cnt].v=b; mst[cnt].w=ed[i].w; uni(a,b);//就把起点和终点连接起来（放入一个集合） sum+=ed[i].w;//把这条边的长度加入最小生成树长度 //最小生成树最多只能有n-1条边 if(cnt==n-1) break; } } for(int i=1;i<=cnt;i++){ cout<<mst[i].u<<" "<<mst[i].v; cout<<endl; } return 0; }

2. 算法二：朴素 Prim 算法 (邻接矩阵)

核心思想：贪心策略，以点为核心。

1. 维护一个集合，初始只有一个起点。

2. 每次在集合外寻找离集合最近的一个点（遍历dis数组），把它拉入集合。

3. 用这个新加入的点去松弛（更新）它邻居的距离。

适用场景：稠密图（点少边极多，如完全图）。

复杂度：O(N^2)

//朴素prim 邻接矩阵+prim #include <iostream> #include <cstring>//对应memset using namespace std; int n,e; int g[110][110]; int vis[110];//记录每个点是否已经被点亮（加入集合） int dis[110];//记录每个点到集合的距离 int pre[110];//记录每个点的前驱（被谁更新的） long long sum;//记录最小生成树的总长度（工程的总造价） void prim(int s){ dis[s]=0;//起点到集合的距离为0； for(int i=1;i<=n;i++){//n个点循环n次 //每次未被点亮的且dis最小的点加入集合，然后更新它的邻接点的dis int p=0; for(int j=1;j<=n;j++){ if(vis[j]==0 && dis[j]<dis[p]) p=j; } //如果循环完了p还是0，或者dis[p]还是无穷大 //说明剩下的点和集合都不连通，无法构成生成树 if(p==0 || dis[p]==0x3f3f3f3f) break; //每次未被点亮的且dis最小的点加入集合，然后更新它的邻接点的dis vis[p]=1; sum+=dis[p];//更新最小生成树权值（总造价） //第一次会点亮起点，起点的前驱是自己不需要连线 if(p!=pre[p]) //连接每个点亮的点和它的前驱节点（经过这个前驱节点到集合距离最短） cout<<pre[p]<<" "<<p<<endl; for(int j=1;j<=n;j++){ //当该邻接点没有被点亮且邻接点到集合的距离大于邻接点通过p点到集合的距离时 //更新邻接点到集合的距离为邻接点通过p点到集合的距离 if(dis[j]>g[p][j]&&vis[j]==0){ dis[j]=g[p][j]; pre[j]=p;//被p更新，即前驱为p } } } } int main(){ cin>>n>>e;//城市数 边数 memset(g,0x3f,sizeof(g));//初始化邻接矩阵边权为无穷 memset(dis,0x3f,sizeof(dis));//初始化每个点到集合的距离为无穷 for(int i=1;i<=n;i++) pre[i]=i;//初始化每个点自成集合，自己被自己更新 for(int i=1;i<=n;i++) g[i][i]=0;//初始化每个点到自己距离为0 //邻接矩阵存图 for(int i=1;i<=e;i++){ int u,v,w; cin>>u>>v>>w; if(u!=v && w<g[u][v]) g[u][v]=g[v][u]=w; } prim(1);//以第一个城市为起点 return 0; }

3. 算法三：堆优化 Prim 算法 (邻接表)

核心思想：

在朴素 Prim 的基础上，用优先队列（堆）来替代“寻找最近点”的循环过程，将找最小值的时间复杂度从O(N)降为O(log N)。

配合邻接表存图，非常适合处理大规模稀疏图。

技巧：使用pre数组记录路径，最后统一输出。

适用场景：大规模稀疏图（N, M很大），是竞赛中替代 Kruskal 的备选方案。

复杂度：O(M log N)

//临接表+堆优化prim #include <iostream> #include <queue> #include <cstring>//对应memset函数 using namespace std; struct node{ int id;//点编号 int w;//到集合的距离 //优先队列默认大根堆，重载运算符修改为小根堆 friend bool operator<(node a,node b){ return a.w>b.w; } }; priority_queue<node> q; int h[110];//存临接表头指针数组 int vtex[20010];//存第i条边终点的下标 int nxt[20010];//存第i条边同起点的下一条边的索引 int wt[20010];//存第i条边边权 int pre[110];//存每个点的前驱（即通过前驱到集合的距离是最短的） int n,e; int dis[110];//存每个节点到集合的距离 int idx; int vis[110];//标记每个节点是否已经在集合中（被点亮） long long sum;//记录最小生成树长度 void prim(int s){ dis[s]=0;//起点到集合距离为0 node tmp; tmp.id=s; tmp.w=0; q.push(tmp);//起点入队 while(!q.empty()){ tmp=q.top();//访问队首元素 q.pop();//队首出队 int nid=tmp.id; if(vis[nid]==1) continue;//如果该点已经出队过（被点亮）就跳过 vis[nid]=1;//否则就点亮它（加入集合） sum+=dis[nid];//更新最小生成树长度（工程总造价） int p=h[nid]; while(p!=-1){//遍历当前点亮的点点所有临接点 //当邻接点没有被点亮过且到集合的距离大于边权 就更新到集合的距离并入队 if(vis[vtex[p]]==0 && dis[vtex[p]]>wt[p]){ dis[vtex[p]]=wt[p]; q.push({vtex[p],wt[p]}); //被哪个点更新，前驱就是谁 pre[vtex[p]]=nid; } p=nxt[p];//更新指针 } } } void addedge(int u,int v,int w){ vtex[idx]=v; nxt[idx]=h[u]; wt[idx]=w; h[u]=idx++; } int main(){ cin>>n>>e;//城市数 边数 for(int i=1;i<=n;i++) pre[i]=i;//初始化所有节点自成集合（前驱为自己） memset(h,-1,sizeof(h));//初始化头指针数组为空 memset(dis,0x3f,sizeof(dis));//初始化dis数组为无穷 //临接表存图 for(int i=1;i<=e;i++){ int u,v,w; cin>>u>>v>>w; addedge(u,v,w);//无向边需要加双向边 addedge(v,u,w); } prim(1);//从1号点进入 for(int i=1;i<=n;i++){ if(pre[i]!=i) cout<<pre[i]<<" "<<i<<endl; } return 0; }

4. 总结：如何选择？

建议：

1. 一般题目（N<=10^5），首选Kruskal，代码逻辑最简单。

2. 如果是完全图或者N<=3000但M很大，用朴素Prim。

3. 如果需要以特定点为根生长，或者卡常数，用堆优化Prim。