茶叶手机网站建设,自动做网站,房屋装修设计图,网站制作实验报告题解#xff1a;选点#xff0c;选最小权的边#xff0c;更新点权。可以手动自行找一遍怎么找到这个最小的生成树#xff0c;随便选一个点放入我们选的集合中#xff0c;然后看和这个点相连的点中#xff0c;与那个点相连的那条边权值是最小的#xff0c;选择之后#… 题解选点选最小权的边更新点权。可以手动自行找一遍怎么找到这个最小的生成树随便选一个点放入我们选的集合中然后看和这个点相连的点中与那个点相连的那条边权值是最小的选择之后把相连的这个点一起放入集合中这样的话集合中就多了一点现在要找和这两个点都相连的点中那个边的权最小直到全部的点都在集合中就完成了。 #include iostream
#include bits/stdc.h
using namespace std;
int inf 0x3fffff;
int gra[1005][1005];
int vis[1005];
int dist[1005];
void prim(int n)
{memset(vis,0,sizeof(vis));for(int i 0; i n; i ) dist[i] gra[1][i];int Min inf, v, flag 1;for(int i 1; i n; i ){Min inf;for(int j 1; j n; j ){if(!vis[j] dist[j] Min){Min dist[j];v j;}}if(Min inf) {flag 0;break;}vis[v] 1;for(int j 1; j n; j ){if(!vis[j] dist[j] gra[v][j]){dist[j] gra[v][j];}}}int ans 0;for(int i 1; i n;i ){ans dist[i];}if(flag)printf(%d\n,ans);else printf(-1\n);
}
int main()
{int n,m,u,v,w;while(~scanf(%d%d,n,m)){for(int i 0; i n; i ){for(int j 0; j n; j ){if(i j) gra[i][j] 0;else gra[i][j] inf;}}for(int i 0; i m; i ){scanf(%d%d%d,u,v,w);gra[u][v] gra[v][u] w;}prim(n);}return 0;
} 转载于:https://www.cnblogs.com/lcchy/p/10139425.html
