usingnamespace std; constint N = 510; int g[N][N];//存储图 int dist[N];//存储每个节点到当前联通部分的距离 int state[N];//存储每个点是否被加入联通部分中 int pre[N];//每个点联通时的前置节点 int n,m;
voidgetpath(){ int res = 0; //先将所有节点的前置节点置-1 memset(pre, -1, sizeof(pre)); memset(dist, 0x3f, sizeof(dist)); //将1节点的距离置0 dist[1] = 0;
for(int t= 0; t<n; t++){ //查找所有节点中距离联通部分最近的点,加入联通部分 int midist = 0x3f; int index = -1; //设置t=-1是为了保留孤立点 for(int i=1; i<=n; i++){ if((index==-1 || dist[i]<dist[index]) && state[i]==0){ midist = dist[i]; index = i; }
voidkruskal(){ int res = 0; int cnt =0 ; for(int i =1; i<=m; i++){ int pa = findp(edg[i].a); int pb = findp(edg[i].b); if(pa!=pb){ res += edg[i].w; p[pa] = pb; cnt ++;