Prim——最小生成树

Description 给你一个具有n个点，m条边的无向连通图，求其最小生成树的权值和。 Input 第一行两个整数n(1<=n<=300)和m，分别表示图的顶点数和边数。 接下来m行是每行三个整数u, v, c，表示结点u和v之间有边相连，权值为c(1≤c≤10000)。 Output 输出文件仅一个整数为最小生成树的权值和。 Sample Input 3 3 1 2 5 2 3 3 1 3 1 Sample Output 4 ------------ ```cpp #include<bits/stdc++.h> #define inf 0x7fffffff using namespace std; int n,m; struct eg { int next,to,value; }a[100000]; void fin(int &x) { scanf("%d",&x); } int h[100000]; int cnt; int d[100000]; int vis[100000]; int ans; void Union(int x,int y,int z) { cnt++; a[cnt].next=h[x]; a[cnt].to=y; a[cnt].value=z; h[x]=cnt; } int main() { fin(n); fin(m); for(int i=1;i<=m;i++) { int x,y,z; fin(x); fin(y); fin(z); Union(x,y,z); Union(y,x,z); } fill(d+1,d+n+1,inf); d[1]=0; for(int i=1;i<=n;i++) { int minn=0x7fffffff; int k; for(int o=1;o<=n;o++)if(d[o]<minn&&vis[o]==0)minn=d[o],k=o; vis[k]=1; ans+=d[k]; for(int o=h[k];o;o=a[o].next) { int to=a[o].to; if(vis[to]==0) { d[to]=min(d[to],a[o].value); } } } cout<<ans; } ``` ------------ # 注意prim的状态转移方程 ## Prim：d[to]=min(d[to], **a[o].value** ); ## Dijkstra：d[to]=min(d[to], **a[o].value+d[k]** ); # 区别： ## Prim: d[i]表示i节点到最小生成树的集合的最短距离 ## Dijkstra: d[i]表示i节点到单源点的最短距离 ------------ # 注意 一共prim了n次点，所以外层循环是1~n ## 但注意请勿犯 for(int i=1;i<=n;i++) { for(int i=1;i<=n;i++) { ... } } ## 这样的错 ------------