无向图最小生成树（prim算法）

无向图最小生成树（prim算法）

输入

第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。（2 <= N <= 1000, 1 <= M <= 50000) 第2 - M + 1行：每行3个数S E W，分别表示M条边的2个顶点及权值。(1 <= S, E <= N，1 <= W <= 10000)

输出

输出最小生成树的所有边的权值之和。

输入示例

9 141 2 42 3 83 4 74 5 95 6 106 7 27 8 18 9 72 8 113 9 27 9 63 6 44 6 141 8 8

输出示例

37

#include #include #include using namespace std;#define MAX 1005#define INF 0x7fffffffint N,M,S,E,W;vector > val(MAX,vector(MAX,INF));long long prim(){ long long res=0; vector vis(MAX,false); vector min(MAX,INF); min[1]=0; for(int i=1;i<=N;i++){ int j,k; for(k=-1,j=1;j<=N;j++) if(!vis[j]&&(k==-1||min[j]>N>>M; for(int i=0;i>S>>E>>W; val[S][E]=val[E][S]=W; } cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。