（1）prim
*时间复杂度O(n^2); *最小生成树； *稠密图适用； *与dijskra仅有一行有区别；
int d[10010],dis[10010][10010]; bool vis[10010]; int x,y,len,n,m; void prim(int s) { memset(vis,0,sizeof(vis)); for (int i=1;i<=n;i++) d[i]=dis[s][i]; vis[s]=1; d[s]=0; for (int i=1;i<n;i++) { int mn=inf; int k=0; for (int j=1;j<=n;j++) if (!vis[j]&&d[j]<mn) mn=d[j],k=j; vis[k]=1; for (int j=1;j<=n;j++) if (!vis[j]) d[j]=min(d[j],dis[k][j]); //唯一的区别==； } } int main() { scanf("%d%d",&n,&m); memset(dis,0x3f,sizeof(dis)); for (int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&len); dis[x][y]=len; } for (int i=1;i<=n;i++) dis[i][i]=0; prim(1); long long ans=0; for (int i=2;i<=n;i++) ans+=d[i]; printf("%d",ans); return 0; } （2）kruscal
*时间复杂度O(mlogm+na(n)),a(n)表示并查集常数； *基于贪心和并查集思想； *stl快排一遍后从小到大加边；
int num=0,x,y,len; int fa[100001]; struct mc { int x,y,len; bool operator< (const mc b) const { return len<b.len; } }e[100010]; void put(int x,int y,int len) { num++; e[num].x=x; e[num].y=y; e[num].len=len; } int get(int x) { if (fa[x]==x) return x; else return get(fa[x]); } int main() { int n,m; scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&len); put(x,y,len); } sort(e+1,e+num+1); for (int i=1;i<=n;i++) fa[i]=i; long long total=0,ans=0; for (int i=1;i<=num;i++) { int f1=get(e[i].x); int f2=get(e[i].y); if(f1!=f2) { fa[f1]=f2; total++; ans+=e[i].len; if (total==n-1) break; } } printf("%d",ans); }