企业官网建设流程全解析

目录Kruskal 算法模版Prim 算法模版D 题有线通讯网E 题卫星通讯网F 题Building RoadsKruskal 算法模版#include bits/stdc.h using namespace std; using LL long long; const int N 1e5 50; struct Edge{ int u, v, w; bool operator (const Edge o) const { return w o.w; } } e[N]; int n, m; int fa[N]; int cnt; // 并查集初始化 void init(){/*略*/} // 并查集查找 int find(int x){/*略*/} // 并查集合并 void merge(int x, int y){/*略*/} LL Kruskal(){ // 边权和 LL sum 0; int cnt n; // 连通分量个数 // 初始化并查集 init(); // 按边权从小到大排序 sort(e 1, e m 1); // 从边权小的边开始添加 for(int i 1; i m; i){ int u e[i].u, v e[i].v, w e[i].w; if(find(u) find(v)) continue; // 已在图中跳过该边 // 添加边 u, v相当于合并 u 和 v 所在的集合 sum w; merge(u, v); cnt--; // 连通分量个数减 1 } if(cnt 1) return -1; return sum; } int main(){ cin n m; for(int i 1; i m; i) { cin e[i].u e[i].v e[i].w; } cout Kruskal(); return 0; }Prim 算法模版int e[N][N]; // 邻接矩阵 bool vis[N]; // vis[u] 表示 u 是否在 MST 中 int n, d[N]; // d[u] 表示点 u 到 MST 的最短距离 LL Prim(){ // 初始化 memset(vis, false, sizeof(vis)); memset(d, 0x3f, sizeof(d)); // 边权和 LL sum 0; d[1] 0; // 让第一轮选出点 1 for(int i 1; i n; i){ // 一共需要 n 轮选点 int u -1; for(int v 1; v n; v){ // 选出未访问且距离 MST 最近的点 if(!vis[v] (u -1 || d[v] d[u])) u v; } // 离 MST 最近的点的距离为无穷大则不连通 if(d[u] INF) return -1; // 点 u 加入 MST sum d[u]; vis[u] true; // 以点 u 更新其他点到 MST 的距离 for(int v 1; v n; v){ if(!vis[v]) d[v] min(d[v], e[u][v]); } } return sum; }D 题有线通讯网知识点Prim 算法思路该题要求对 n 座城市铺设 n - 1 条光缆并要求所有城市连通那本质上是一棵树又要求铺设光缆的费用最低即要求选取的 n - 1 条光缆的长度最小自然想到这题其实是求最小生成树并求对应的边权和。由题意知任意两点之间的边权等于两点之间的距离由于此题边数很大任意两点之间都有一条边因此考虑使用 Prim 算法解决易错点注意边权为浮点数#include bits/stdc.h using namespace std; using LL long long; const int N 5e3 50; bool vis[N]; // vis[u] 表示 u 是否在 MST 中 double d[N]; // d[u] 表示点 u 到 MST 的最短距离 int x[N], y[N]; int n; double dis(int u, int v){/*略*/} double Prim(){ memset(vis, false, sizeof(vis)); for(int i 1; i n; i) d[i] 1e18; double sum 0; d[1] 0; for(int i 1; i n; i){ // n 轮选点 int u -1; for(int v 1; v n; v){ // 选出未访问且距离 MST 最近的点 if(!vis[v] (u -1 || d[v] d[u])){ u v; } } // u 加入 MST sum d[u]; vis[u] true; // 以点 u 更新其他点到 MST 的距离 for(int v 1; v n; v){ // u 到 v 的边权为欧几里得长度 if(!vis[v]) d[v] min(d[v], dis(u, v)); } } return sum; } int main(){ cin n; for(int i 1; i n; i) cin x[i] y[i]; cout fixed setprecision(10) Prim(); return 0; }E 题卫星通讯网知识点Prim 算法思路题目的意思是给定 n 个点要求将其分成 k 个连通块使得总的边权和最小。先从简单的想起假设 k 1要想使得总边权和最小那自然是最小生成树的边权和。再考虑 k 2这时可以多分出一个连通块那么显然去掉最小生成树中的一条边就可以变成两个连通块显然应该去掉之前最小生成树中权值最大的边。同理依次类推如果要分成 k 个连通块只需要删除边权最大的 k - 1 条边即可可以在进行 Prim 算法的时候通过一个大根堆来存储所有边权最后从答案中去掉边权最大的 k - 1 条边即可#include bits/stdc.h using namespace std; using LL long long; const int N 5e3 50; bool vis[N]; // vis[u] 表示 u 是否在 MST 中 double d[N]; // d[u] 表示点 u 到 MST 的最短距离 priority_queuedouble qMax; // 存储 MST 中边的边权 int x[N], y[N]; int n, k; double dis(int u, int v){/*略*/} double Prim(){/*略*/} int main(){ cin n k; for(int i 1; i n; i) cin x[i] y[i]; double ans Prim(); // 可去掉 k-1 条边优先去掉边权大的 for(int i 1; i k; i){ ans - qMax.top(); qMax.pop(); } cout fixed setprecision(10) ans endl; return 0; }F 题Building Roads知识点最小生成树思路原问题可以成是一个有着 n 个节点的完全图实质上为最小生成树求解的问题连通所有节点且总边权和最小其中已有的边可以认为边权为 0不会对答案产生贡献。原图可以视为一个完全图边数较多考虑使用 prim 算法解决由于 n 只有 1000用 kruskal 算法解决也可以#include bits/stdc.h using namespace std; using LL long long; const int N 1e3 50; bool vis[N]; // vis[u] 表示 u 是否在 MST 中 double d[N]; // d[u] 表示点 u 到 MST 的最短距离 double e[N][N]; int x[N], y[N]; int n, m; double dis(int u, int v){/*略*/} double Prim(){/*略*/} int main(){ cin n m; for(int i 1; i n; i) cin x[i] y[i]; // 计算完全图的边权 for(int i 1; i n; i){ for(int j 1; j n; j){ e[i][j] dis(i, j); } } // 认为初始边的边权为 0 for(int i 1; i m; i){ int u, v; cin u v; e[u][v] 0; e[v][u] 0; } cout fixed setprecision(2) Prim() endl; return 0; }