深圳微商城网站制作,宜宾网站网站建设,企拓客软件多少钱,马关县住房和城乡建设局网站最小生成树问题是指给定一个带权的无向图#xff0c;删除一些边使得这个无向图变成一棵树#xff0c;并且权值之和最小。
解决此类问题的方法主要有两种#xff1a;Prim算法#xff0c;Kruskal算法
Prim 算法
从一个点开始#xff0c;逐步扩展#xff0c;每次选择权值…最小生成树问题是指给定一个带权的无向图删除一些边使得这个无向图变成一棵树并且权值之和最小。
解决此类问题的方法主要有两种Prim算法Kruskal算法
Prim 算法
从一个点开始逐步扩展每次选择权值最小的相连的边保证不出环直到顶点总数等于图中所有顶点个数组成最小生成树
例题 最小生成树
P3366 【模板】最小生成树
#includebits/stdc.h
using namespace std;
int fa[500005],n,m,ans,cnt;
int vis[100005],dis[100005],g[5005][5005];
void prim(){memset(vis,0,sizeof vis);memset(dis,0x3f,sizeof dis);dis[1]0;for(int i1;in;i){int t-1;for(int j1;jn;j){if(!vis[j](t-1||dis[j]dis[t])){tj;}}if(dis[t]0x3f3f3f3f){printf(orz\n);return ;}vis[t]1;ansdis[t];for(int j1;jn;j){if(dis[j]g[t][j]!vis[j]){dis[j]g[t][j];}}}printf(%d\n,ans);
}
int main(){scanf(%d%d,n,m);memset(g,0x3f,sizeof g);for(int i1;im;i){ int xx,yy,zz;scanf(%d%d%d,xx,yy,zz);if(g[xx][yy]0x3f3f3f3f){g[xx][yy]zz;g[yy][xx]zz;}else{g[xx][yy]min(zz,g[xx][yy]);g[yy][xx]min(zz,g[yy][xx]);}}prim();return 0;
}Kruskal 算法
把所有边都从小到大排好序从小到大逐个放入树保证不能出环直至树中结点总个数等于原无向图顶点数
例题 最小生成树
P3366 【模板】最小生成树
#includebits/stdc.h
using namespace std;
int fa[100005],n,m,ans,cnt;
struct node{int x,y,z;
}a[200005];
int Find(int x){if(fa[x]x){return x;}return fa[x]Find(fa[x]);
}
bool cmp(node aa,node bb){return aa.zbb.z;
}
int kruskal(){sort(a1,am1,cmp);for(int i1;im;i){int xxFind(a[i].x);int yyFind(a[i].y);if(xxyy){continue;}ansa[i].z;fa[yy]xx;if(cntn-1){return ans;}}return -1;
}
void Init(){for(int i1;in;i){fa[i]i;}
}
int main(){scanf(%d%d,n,m);Init();for(int i1;im;i){scanf(%d%d%d,a[i].x,a[i].y,a[i].z);}if(kruskal()-1){printf(orz\n);return 0;}printf(%d\n,ans);return 0;
}Build
给定几个城镇的坐标要让它们联通起来在它们间
#includebits/stdc.h
using namespace std;
long long fa[500005],n,ans,cnt;
struct node2{long long x,y,z;
}b[500005];
struct node{long long x,y,z;
}a[500005];
long long Find(long long x){if(fa[x]x){return x;}return fa[x]Find(fa[x]);
}
bool cmp1(node2 aa,node2 bb){return aa.xbb.x;
}
bool cmp2(node2 aa,node2 bb){return aa.ybb.y;
}
bool cmp(node aa,node bb){return aa.zbb.z;
}
void kruskal(){sort(a1,a2*n1,cmp);for(int i1;i2*n;i){long long xa[i].x;long long ya[i].y;long long xxFind(x);long long yyFind(y);if(xxyy){continue;}fa[xx]yy;ansa[i].z;cnt;if(cntn-1){return ;}}
}
void Init(){for(int i1;in;i){fa[i]i;}
}
int main(){scanf(%lld,n);Init();for(int i1;in;i){ scanf(%lld%lld,b[i].x,b[i].y);b[i].zi;}sort(b1,bn1,cmp1);for(int i1;in;i){a[i].xb[i].z;a[i].yb[i1].z;a[i].zb[i1].x-b[i].x;}sort(b1,bn1,cmp2);for(int i1;in;i){a[in].xb[i].z;a[in].yb[i1].z;a[in].zb[i1].y-b[i].y;}kruskal();printf(%lld\n,ans);return 0;
}
