php框架做网站的好处,用dw做网站首页,怎么做网站板块,怎么做好推广是什么#xff1a;
一个有 n 个结点的连通图的生成树是原图的极小连通子图#xff0c;且包含原图中的所有 n 个结点#xff0c;并且有保持图连通的最少的边。
kruskal算法#xff1a;
#includeiostream
#includevector
#includealgorithm
#incl…是什么
一个有 n 个结点的连通图的生成树是原图的极小连通子图且包含原图中的所有 n 个结点并且有保持图连通的最少的边。
kruskal算法
#includeiostream
#includevector
#includealgorithm
#includecstdio
#includecstring
using namespace std;
struct node {int x,y,t;
};
int n,m,fa[100001];
int mincost;
bool cmp(node a,node b) {return a.tb.t;
}
int find(int x) {if(fa[x]x) return x;else return find(fa[x]);
}
int main() {while(cinn) {if(n0) return 0;mincost0;memset(fa,0,sizeof(fa));vectornode g;cinm;for(int i1; in; i) fa[i]i;int x,y,t;for(int i1; im; i) {cinxyt;g.push_back((node) {x,y,t});}sort(g.begin(),g.end(),cmp);for(int i0; ig.size(); i) {int ug[i].x;int vg[i].y;double wg[i].t;if(find(u)!find(v)) {mincostw;fa[find(u)]find(v);}}coutmincostendl;}
}时间复杂度O(mlogm) m为边数
prim算法
#includeiostream
#includecstring
using namespace std;
bool vis[101];
int n,x,y,z,ans0,d[101]{1,},g[101][101];
int prim(int s){int indexs;vis[s]true;for(int i1;in;i)d[i]g[s][i];for(int i1;in;i){int minn99999999;for(int j1;jn;j){if(!vis[j]d[j]minn){minnd[j];indexj;}}vis[index]true;ansminn;for(int j1;jn;j){if(!vis[j]d[j]g[index][j]){d[j]g[index][j];}}}
}
int main(){cinn;for(int i1;in;i){for(int j1;jn;j){cing[i][j];}}prim(1);coutans;return 0;
}时间复杂度O(n^2) 主要用于稠密图尤其是完全图的最小生成树
拓展次小生成树
普及版
#includeiostream
#includecstdio
#includevector
#includealgorithm
using namespace std;
const int inf1e9;
struct node{int u,v,w,vis;
}e[20010];
vectorint g[2005];
int n,m,fa[2005],len[2005][2005];
int minn,nd;
bool cmp(node a,node b) {if(a.w!b.w)return a.wb.w;if(a.u!b.u)return a.ub.u;return a.vb.v;
}
int find(int x) {if(x!fa[x])return fa[x]find(fa[x]);return fa[x];
}
int main(){scanf(%d%d,n,m);for(int i1;im;i){scanf(%d%d%d,e[i].u,e[i].v,e[i].w);}sort(e1,em1,cmp);for(int i0;in;i){g[i].clear();g[i].push_back(i);fa[i]i;}minn0;for(int i1;im;i){int xfind(e[i].u);int yfind(e[i].v);if(x!y){e[i].vis1;minne[i].w;int ag[x].size();int bg[y].size();for(int j0;ja;j)for(int k0;kb;k)len[g[x][j]][g[y][k]]len[g[y][k]][g[x][j]]e[i].w;fa[x]y;int cpy[110];for(int j0;jb;j)cpy[j]g[y][j];for(int j0;ja;j)g[y].push_back(g[x][j]);for(int j0;jb;j)g[x].push_back(cpy[j]);}}ndinf;for(int i1;im;i)if(!e[i].vis)ndmin(nd,minne[i].w-len[e[i].u][e[i].v]);printf(%d\n,nd);return 0;
}提高版
严格次小生成树
博客
Boruvka算法
博客
时间复杂度O((nm)logn)
常用于解决这类问题给你n个点每个点有点权任意两个点之间有边权边权为两个点权用过某种计算方式得出求最小生成树。
题目 题解
