企业官网建设流程全解析

网站建设费用主要包括哪些方面,怎么制作个人网页教程,沈阳人流哪个医院好安全,网站免费推广方式【题目描述】有一张城市地图#xff0c;图中的顶点为城市#xff0c;无向边代表两个城市间的连通关系#xff0c;边上的权为在这两个城市之间修建高速公路的造价#xff0c;研究后发现#xff0c;这个地图有一个特点#xff0c;即任一对城市都是连通的。现在的问题是图中的顶点为城市无向边代表两个城市间的连通关系边上的权为在这两个城市之间修建高速公路的造价研究后发现这个地图有一个特点即任一对城市都是连通的。现在的问题是要修建若干高速公路把所有城市联系起来问如何设计可使得工程的总造价最少【输入】n城市数1≤n≤100e边数以下e行每行3个数i,j,wij表示在城市i,j之间修建高速公路的造价。【输出】n-1行每行为两个城市的序号表明这两个城市间建一条高速公路。【输入样例】5 8 1 2 2 2 5 9 5 4 7 4 1 10 1 3 12 4 3 6 5 3 3 2 3 8【输出样例】1 2 2 3 3 4 3 51. 算法一Kruskal 算法 (克鲁斯卡尔)核心思想贪心策略以边为核心。将所有边按照权值从小到大排序。依次枚举每一条边利用并查集判断该边的两个端点是否已经连通。如果不连通就选中这条边并合并集合如果已连通则跳过。适用场景稀疏图点多边少竞赛中最常用的写法代码短且不易错。复杂度O(M log M)//第一种方法kruskal #include iostream #include algorithm//对应sort函数 using namespace std; int n,e; int fa[110];//存储每个节点所在集合的老大 struct edge{ int u;//边起点 int v;//边终点 int w;//边权 //重载运算符按照边权从小到大排序 friend bool operator (edge a,edge b){ return a.wb.w; } }ed[20010];//边集数组 edge mst[20010];//记录最小生成树的边 long long sum;//记录最短工程总造价 int cnt;//记录连起来的边数 //并查集查询路径压缩 int find(int a){ if(fa[a]a) return a;//如果已经是根结点就返回 //否则就递归找根节点并将根结点变成路径上每个节点的祖先节点 return fa[a]find(fa[a]); } //并查集合并 void uni(int x,int y){ int faxfind(x);//找到x的集合中老大 int fayfind(y);//找到y的集合中老大 //如果老大是同一个无事发生否则就让x的祖先变成y的祖先的祖先(合并为一个集合) if(fax!fay){ fa[fay]fax; } } int main(){ cinne;//城市数 边数 for(int i1;ie;i) cined[i].ued[i].ved[i].w; //将边集数组按边权从小到大排序 注意这里是ede1不是edn1 sort(ed1,ede1); for(int i1;in;i) fa[i]i;//初始化每个城市自成集合 for(int i1;ie;i){//遍历所有边按照边权从小到大 int aed[i].u; int bed[i].v; if(find(a)!find(b)){//如果这条边的起点和终点不在一个集合 cnt;//连起来的边数1 mst[cnt].ua; mst[cnt].vb; mst[cnt].wed[i].w; uni(a,b);//就把起点和终点连接起来放入一个集合 sumed[i].w;//把这条边的长度加入最小生成树长度 //最小生成树最多只能有n-1条边 if(cntn-1) break; } } for(int i1;icnt;i){ coutmst[i].u mst[i].v; coutendl; } return 0; }2. 算法二朴素 Prim 算法 (邻接矩阵)核心思想贪心策略以点为核心。维护一个集合初始只有一个起点。每次在集合外寻找离集合最近的一个点遍历dis数组把它拉入集合。用这个新加入的点去松弛更新它邻居的距离。适用场景稠密图点少边极多如完全图。复杂度O(N^2)//朴素prim 邻接矩阵prim #include iostream #include cstring//对应memset using namespace std; int n,e; int g[110][110]; int vis[110];//记录每个点是否已经被点亮加入集合 int dis[110];//记录每个点到集合的距离 int pre[110];//记录每个点的前驱被谁更新的 long long sum;//记录最小生成树的总长度工程的总造价 void prim(int s){ dis[s]0;//起点到集合的距离为0 for(int i1;in;i){//n个点循环n次 //每次未被点亮的且dis最小的点加入集合然后更新它的邻接点的dis int p0; for(int j1;jn;j){ if(vis[j]0 dis[j]dis[p]) pj; } //如果循环完了p还是0或者dis[p]还是无穷大 //说明剩下的点和集合都不连通无法构成生成树 if(p0 || dis[p]0x3f3f3f3f) break; //每次未被点亮的且dis最小的点加入集合然后更新它的邻接点的dis vis[p]1; sumdis[p];//更新最小生成树权值总造价 //第一次会点亮起点起点的前驱是自己不需要连线 if(p!pre[p]) //连接每个点亮的点和它的前驱节点经过这个前驱节点到集合距离最短 coutpre[p] pendl; for(int j1;jn;j){ //当该邻接点没有被点亮且邻接点到集合的距离大于邻接点通过p点到集合的距离时 //更新邻接点到集合的距离为邻接点通过p点到集合的距离 if(dis[j]g[p][j]vis[j]0){ dis[j]g[p][j]; pre[j]p;//被p更新即前驱为p } } } } int main(){ cinne;//城市数 边数 memset(g,0x3f,sizeof(g));//初始化邻接矩阵边权为无穷 memset(dis,0x3f,sizeof(dis));//初始化每个点到集合的距离为无穷 for(int i1;in;i) pre[i]i;//初始化每个点自成集合自己被自己更新 for(int i1;in;i) g[i][i]0;//初始化每个点到自己距离为0 //邻接矩阵存图 for(int i1;ie;i){ int u,v,w; cinuvw; if(u!v wg[u][v]) g[u][v]g[v][u]w; } prim(1);//以第一个城市为起点 return 0; }3. 算法三堆优化 Prim 算法 (邻接表)核心思想在朴素 Prim 的基础上用优先队列堆来替代“寻找最近点”的循环过程将找最小值的时间复杂度从O(N)降为O(log N)。配合邻接表存图非常适合处理大规模稀疏图。技巧使用pre数组记录路径最后统一输出。适用场景大规模稀疏图N, M很大是竞赛中替代 Kruskal 的备选方案。复杂度O(M log N)//临接表堆优化prim #include iostream #include queue #include cstring//对应memset函数 using namespace std; struct node{ int id;//点编号 int w;//到集合的距离 //优先队列默认大根堆重载运算符修改为小根堆 friend bool operator(node a,node b){ return a.wb.w; } }; priority_queuenode q; int h[110];//存临接表头指针数组 int vtex[20010];//存第i条边终点的下标 int nxt[20010];//存第i条边同起点的下一条边的索引 int wt[20010];//存第i条边边权 int pre[110];//存每个点的前驱即通过前驱到集合的距离是最短的 int n,e; int dis[110];//存每个节点到集合的距离 int idx; int vis[110];//标记每个节点是否已经在集合中被点亮 long long sum;//记录最小生成树长度 void prim(int s){ dis[s]0;//起点到集合距离为0 node tmp; tmp.ids; tmp.w0; q.push(tmp);//起点入队 while(!q.empty()){ tmpq.top();//访问队首元素 q.pop();//队首出队 int nidtmp.id; if(vis[nid]1) continue;//如果该点已经出队过被点亮就跳过 vis[nid]1;//否则就点亮它加入集合 sumdis[nid];//更新最小生成树长度工程总造价 int ph[nid]; while(p!-1){//遍历当前点亮的点点所有临接点 //当邻接点没有被点亮过且到集合的距离大于边权 就更新到集合的距离并入队 if(vis[vtex[p]]0 dis[vtex[p]]wt[p]){ dis[vtex[p]]wt[p]; q.push({vtex[p],wt[p]}); //被哪个点更新前驱就是谁 pre[vtex[p]]nid; } pnxt[p];//更新指针 } } } void addedge(int u,int v,int w){ vtex[idx]v; nxt[idx]h[u]; wt[idx]w; h[u]idx; } int main(){ cinne;//城市数 边数 for(int i1;in;i) pre[i]i;//初始化所有节点自成集合前驱为自己 memset(h,-1,sizeof(h));//初始化头指针数组为空 memset(dis,0x3f,sizeof(dis));//初始化dis数组为无穷 //临接表存图 for(int i1;ie;i){ int u,v,w; cinuvw; addedge(u,v,w);//无向边需要加双向边 addedge(v,u,w); } prim(1);//从1号点进入 for(int i1;in;i){ if(pre[i]!i) coutpre[i] iendl; } return 0; }4. 总结如何选择算法复杂度核心数据结构适用图类型推荐指数KruskalO(M log M)结构体数组 并查集稀疏图(大多数情况)⭐⭐⭐⭐⭐ (首选)朴素PrimO(N^2)邻接矩阵稠密图(点少边极多)⭐⭐⭐堆优化PrimO(M log N)邻接表 优先队列稀疏图(大数据)⭐⭐⭐⭐建议一般题目N10^5首选Kruskal代码逻辑最简单。如果是完全图或者N3000但M很大用朴素Prim。如果需要以特定点为根生长或者卡常数用堆优化Prim。