简单最小生成树 注意重边
#include <iostream> #include <cstring> using namespace std; int vis[1050],dis,edge[1050][1050],lowc[1050],n,m; int prim() { int i,j,p,maxc,res=0; memset(vis,0,sizeof(vis)); vis[0]=1; for(i=1;i<n;i++) lowc[i]=edge[0][i]; for(i=1;i<n;i++) { maxc=0; p=-1; for(j=0;j<n;j++) { if(!vis[j] && lowc[j]>maxc) { maxc=lowc[j]; p=j; } } if(maxc==0) return -1; res+=maxc; vis[p]=1; for(j=1;j<n;j++) if(!vis[j] && lowc[j]<edge[p][j]) lowc[j]=edge[p][j]; } return res; } int main() { int i,j,x,y,z; scanf("%d%d",&n,&m); /* for(i=0;i<n;i++) for(j=0;j<n;j++) edge[i][j]=-inf;*/ for(i=0;i<m;i++) { scanf("%d%d%d",&x,&y,&z); x--; y--; if(edge[x][y]<z) edge[y][x]=edge[x][y]=z; } printf("%d/n",prim()); return 0; }