C++ 代码
//再写算法的时候,不是都准备好了,像你要遍历的数组的内容,可能很多时候都只有第一个数据,之后的数据一定是要你边去遍历
//边去补充数据的,这里就有点递归思想了:调用自己~~利用自己来达到某种目的
//所以写算法只写到现在目前有数据的范围肯定是不够的!!!
//如果能生成最小生成树了,就找最小的;生不成最小生成树,说明目标点是孤立的!
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510,INF = 0x3f3f3f3f;
int n,m,u,v,w;
int g[N][N],dist[N];
bool st[N];
int prim()
{
int res = 0; //代表:权重之和
for(int i = 0 ; i < n ; i ++)//迭代n次,之后有代码会看看是不是第一次迭代!!!
{
int t = -1;//更新t的血液
for(int j = 1 ; j <= n ;j ++)//点的编号
if( (t == -1 || dist[t] > dist[j] ) && (!st[j]) )
t = j;
//淘汰条件!!!,,需要不是第一次的哦!!!
if(i && dist[t] == INF) return INF;
if(i) res += dist[t];//如果不是孤立点并且不是第一个点的话~
st[t] = true;
for(int j = 1; j <= n ; j++) dist[j] = min(dist[j] , g[t][j]);
}
return res;
}
int main()
{
scanf("%d%d",&n,&m);
memset(dist,0x3f,sizeof dist);
memset(g,0x3f ,sizeof g);
for(int i = 0 ; i < m ;i ++)
{
scanf("%d%d%d",&u,&v,&w);
g[u][v] = g[v][u] = min(g[u][v] , w);
}
int t = prim();
if(t == INF) puts("impossible") ;
else cout << t << endl;
}