想写个Prim(还没判不连通),但就算是联通图也炸了几个点,求调
#include <iostream>
#include <vector>
using namespace std;
struct Edge
{
int v,w;
};
const int INF = 1e9;
vector<Edge> g[5010];
int n,sum;
int mincount[5010];//mincount从最小生成树内的顶点到暂时不在最小生成树内的顶点的最小边权
void Prim()
{
int i,j;
mincount[1] = 0; ////将1加入最小生成树
for(i = 0;i < g[1].size();i++) mincount[g[1][i].v] = g[1][i].w;
for(i = 1;i <= n - 1;i++) //除点1外,枚举最小生成树剩下的n - 1条边
{
int minn = INF,num;
for(j = 1;j <= n;j++) //枚举剩余的点
{
if(mincount[j] != 0&&mincount[j] < minn) //集合外的点mincount不等于0
{
minn = mincount[j];
num = j;
}
}
mincount[num] = 0; //将num加入最小生成树
sum+=minn;
for(j = 0;j < g[num].size();j++) mincount[g[num][j].v] = min(mincount[g[num][j].v],g[num][j].w);
}
}
int main()
{
int m,i;
cin>>n>>m;
for(i = 1;i <= n;i++) mincount[i] = INF;
while(m--)
{
int u,v,w;
cin>>u>>v>>w;
g[u].push_back((Edge){v,w});
g[v].push_back((Edge){u,w});
}
Prim();
cout<<sum;
return 0;
}