将修改后的代码整理出来
时间: 2023-10-08 17:08:40 浏览: 33
好的,这里是修改后的代码,可以输出形如(vi,w,vj)的三元组:
```c++
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int n, m;
int head[MAXN], dis[MAXN], vis[MAXN], cnt;
struct edge
{
int to, w, nxt;
}e[MAXN << 1];
void add(int u, int v, int w)
{
e[++cnt].to = v;
e[cnt].w = w;
e[cnt].nxt = head[u];
head[u] = cnt;
}
void Prim()
{
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for(int i = 1; i <= n; ++i) dis[i] = INF;
dis[1] = 0;
pq.push(make_pair(0, 1));
while(!pq.empty())
{
int u = pq.top().second;
pq.pop();
if(vis[u]) continue;
vis[u] = 1;
for(int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to, w = e[i].w;
if(!vis[v] && dis[v] > w)
{
dis[v] = w;
pq.push(make_pair(dis[v], v));
}
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; ++i)
{
int u, v, w;
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
Prim();
int ans = 0;
for(int i = 2; i <= n; ++i) ans += dis[i];
cout << ans << endl;
for(int i = 2; i <= n; ++i)
{
int u = i, v = 0, w = INF;
for(int j = head[i]; j; j = e[j].nxt)
{
int t = e[j].to;
if(dis[t] == e[j].w && e[j].w < w)
{
v = t;
w = e[j].w;
}
}
if(v) cout << u << " " << w << " " << v << endl;
}
return 0;
}
```
在这段代码中,我们在Prim算法的基础上,增加了一段代码来输出最小生成树的边及权值。具体来说,我们遍历每个点i的相邻边,找到权值等于dis[i]的边中权值最小的那条,记为(u,v,w),然后输出(vi,w,vj)。需要注意的是,我们在遍历相邻边时,只考虑了权值等于dis[i]的边,这是因为只有这些边才可能属于最小生成树。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)