给定一个 n 个点 m 条边的无向图,图中可能存在重边和自环,边权可能为负数。 求最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible。 给定一张边带权的无向图 G=(V,E),其中 V 表示图中点的集合,E 表示图中边的集合,n=|V|,m=|E|。 由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树,其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。
思路:dist[]保留的是每个顶点到树的最小值。
-
先将顶点1放入最小生成树中的顶点集合,并相应的更新dist数组。
-
每次是在最小生成树之外的顶点集合中找出一个最小距离的顶点加入最小生成树中,
-
判断这次寻找的min是否是Inf,如果不是inf就代表能够加入生成树中,如果min等于Inf了就表示不能从中找出n个点组成最小生成树。
- 将这个距生成树最小距离的点来压缩其余各点的距离(其实就是找出这个顶点的出边并更新到dist数组中),在这里一般是对树外集合的点进行压缩,也可以对树中顶点的距离进行压缩,因为对树中顶点的距离压缩不会对整体生成树的价值造成影响。如:
if(book[v]==0&&dist[v]>e[u][v])
或者if(dist[v]>e[u][v])
#include <iostream>
#include <algorithm>
using namespace std;
const int N=510,M=1E5+10,inf=0x3f3f3f3f;
int dist[N],book[N],e[N][N];
int n,m;
void init()
{ for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i==j)
e[i][j]=0;
else e[i][j]=inf;
}
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
e[b][a]=e[a][b]=min(c,e[a][b]); //无向图存储
}
}
int main()
{
cin>>n>>m;
init();
for(int i=1;i<=n;i++)
{
dist[i]=e[1][i];
}
book[1]=1;
int sum=0; //最小生成树的权值
int flag=1;
for(int i=1;i<=n-1&&flag;i++)
{
int minx=inf;
int u;
for(int j=1;j<=n;j++)
{
if(book[j]==0&&minx>dist[j])
//在生成树外的集合中找一个最小距离顶点,因为在生成树中的顶点距离可能会更小
minx=dist[u=j];
}
if(minx==inf)
//记住要用minx来判断是否是无出边,因为用dist[u]来判断可能在本次不循环,但dist[u]保留的是上一次的值而不是Inf
{
flag=0;break;
}
book[u]=1;sum+=dist[u]; //如果有出边顶点的话就加入生成树中
for(int v=1;v<=n;v++)
{
if(book[v]==0&&dist[v]>e[u][v]) // 或者if(dist[v]>e[u][v])
//这里判不判断v是否是生成树中的顶点都可以,因为压缩了生成树中顶点的距离对整体的价值没有影响
dist[v]=e[u][v];
}
}
if(flag)
cout <<sum;
else cout <<"impossible";
}