求图的最小生成树的权值
#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;
typedef struct Enode* Arc;
const int INF=0x3f3f3f3f;
struct Enode
{
int vex;
int w;
Arc next;
};
struct Vnode
{
bool flag;
Arc ed;
Vnode():flag(false),ed(NULL){}
};
struct Vnode Ge[505];
void createGraph(int);
void Add_e(int,Arc);
void Prim(int,int);
int main()
{
int n,m;
cin>>n>>m;
createGraph(m);
Prim(n,m);
return 0;
}
void createGraph(int m)
{
for(int i=0;i<m;i++)
{
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
Arc newnode=new Enode;
newnode->next=NULL;
newnode->vex=v;newnode->w=w;
Add_e(u,newnode);
Arc n2=new Enode;
n2->next=NULL;n2->vex=u;n2->w=w;
Add_e(v,n2);
}
}
void Add_e(int u,Arc newnode)
{
if(Ge[u].ed==NULL)
{
Ge[u].ed=newnode;
}
else
{
Arc cur=Ge[u].ed;
Arc temp=cur->next;
while(temp!=NULL)
{
cur=temp;
temp=temp->next;
}
cur->next=newnode;
}
}
void Prim(int n,int m)
{
bool visited[505];
int minDist[505];
for (int i = 1; i <= n; ++i) {
visited[i] = false;
minDist[i] = INF;
}
minDist[1] = 0;
int sumWeight = 0;
for (int i = 1; i <= n; ++i) {
int minWeight = INF;
int u = -1;
for (int j = 1; j <= n; ++j) {
if (!visited[j] && minDist[j] < minWeight) {
minWeight = minDist[j];
u = j;
}
}
if (u == -1) {
cout << "impossible" << endl;
return; // 无法构成最小生成树
}
visited[u] = true;
sumWeight += minWeight;
for (Arc e = Ge[u].ed; e != NULL; e = e->next) {
int v = e->vex;
int w = e->w;
if (!visited[v] && w < minDist[v]) {
minDist[v] = w;
}
}
}
cout << sumWeight << endl;
}