企业官网建设流程全解析

前言

从图开始的每个算法都挺重要的，用途都很广。

一、最小生成树

1.内容

最小生成树是，在无向有权图中选择一些边，保证所有节点都连通且所有边的总权值最小。

2.Kruskal算法——【模板】最小生成树

#include<bits/stdc++.h> using namespace std; //并查集 vector<int>father; void build(int n) { father.resize(n+1); for(int i=1;i<=n;i++) { father[i]=i; } } int find(int i) { if(i!=father[i]) { father[i]=find(father[i]); } return father[i]; } bool Union(int x,int y)//Union还要负责判断是否为环 -> 在同一集合 { int fx=find(x); int fy=find(y); if(fx!=fy) { father[fx]=fy; return true; } else { return false; } } static bool cmp(vector<int>&a,vector<int>&b) { return a[2]<b[2]; } void solve(int n,int m,vector<vector<int>>&edges) { build(n); //先按边权从小到大排序 sort(edges.begin(),edges.end(),cmp); int ans=0; int edgeCnt=0; for(int i=0;i<m;i++) { if(Union(edges[i][0],edges[i][1])) { edgeCnt++; ans+=edges[i][2]; } } if(edgeCnt==n-1) { cout<<ans; } else { cout<<"orz"; } } void read() { int n,m; cin>>n>>m; vector<vector<int>>edges(m,vector<int>(3)); for(int i=0;i<m;i++) { cin>>edges[i][0]>>edges[i][1]>>edges[i][2]; } solve(n,m,edges); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); read(); return 0; }

Kruskal算法无需建图，但需要借助并查集数据结构与算法：并查集。过程就是先按边权从小到大排序，然后在保证不生成环的情况下，逐渐合并节点，统计总边权。

其中，可以优化Union函数，加入判断是否会生成环，即在同一个集合里。具体方法是让其返回一个bool值，当fx和fy不相等时，在合并后返回true，表示不生成环；否则不合并，返回false，表示会生成环。

3.Prim算法——【模板】最小生成树

孩子们，我来补习了。

#include <bits/stdc++.h> using namespace std; /* /\_/\ * (= ._.) * / > \> */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define dbg(x) cout<<#x<<endl;cout<<x<<endl; #define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl; #define YES cout<<"YES"<<endl;return ; #define Yes cout<<"Yes"<<endl;return ; #define NO cout<<"NO"<<endl;return ; #define No cout<<"No"<<endl;return ; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const int INF=1e9; const ll INFLL=1e18; const int dx[]={-1,1,0,0}; const int dy[]={0,0,-1,1}; const int ddx[]={-2,-1,1,2,2,1,-1,-2}; const int ddy[]={1,2,2,1,-1,-2,-2,-1}; const int MAXN=5000+5; int n,m; vector<vector<pii>>g(MAXN); //手写的堆 vector<vector<int>>heap(MAXN,vector<int>(2)); //反向索引表 //-1没入过堆，-2弹出过 vector<int>where(MAXN,-1); int heapSize=0; int nodeCnt=0; void swap(int i,int j) { int a=heap[i][0]; int b=heap[j][0]; where[a]=j; where[b]=i; swap(heap[i],heap[j]); } void heapInsert(int i) { while(heap[i][1]<heap[(i-1)/2][1]) { swap(i,(i-1)/2); i=(i-1)/2; } } void heapify(int i) { int l=1; while(l<heapSize) { int best=l+1<heapSize&&heap[l+1][1]<heap[l][1]?l+1:l; best=heap[best][1]<heap[i][1]?best:i; if(best==i) { break; } swap(best,i); i=best; l=i*2+1; } } void add(int v,int w) { if(where[v]==-1) { heap[heapSize][0]=v; heap[heapSize][1]=w; where[v]=heapSize++; heapInsert(where[v]); } else if(where[v]>=0) { heap[where[v]][1]=min(heap[where[v]][1],w); heapInsert(where[v]); } } array<int,2> pop() { int u=heap[0][0]; int w=heap[0][1]; swap(0,--heapSize); heapify(0); where[u]=-2; nodeCnt++; return {u,w}; } int prim() { nodeCnt=1; where[1]=-2; for(auto [v,w]:g[1]) { add(v,w); } int ans=0; while(heapSize) { auto [u,w]=pop(); ans+=w; for(auto [v,w]:g[u]) { add(v,w); } } return ans; } void solve() { cin>>n>>m; for(int i=1,u,v,w;i<=m;i++) { cin>>u>>v>>w; g[u].push_back({v,w}); g[v].push_back({u,w}); } int ans=prim(); if(nodeCnt==n) { cout<<ans<<endl; } else { cout<<"orz"<<endl; } } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t=1; //cin>>t; init(); while(t--) { solve(); } return 0; }

先说一下 Prim 算法未优化的过程，就是先准备一个集合存当前访问过的点，这个可以用一个 vis 数组实现，再准备一个小根堆维护所有边。之后随便选一个起始点，将这个点标记，然后把从这个点连出去的所有边加入小根堆。之后，只要堆不为空，每次拿出堆顶的边。若这条边指向的节点没访问过，那么就要这条边，访问这个节点，并把这个节点连出去的边都入堆。否则，即指向的节点访问过了，那么就不要这条边。未优化的 Prim 算法时间复杂度 O(m*logm)。

虽然未优化的复杂度和 Kruskal 一样，但优化后的 Prim 是可以做到 O(n+m)+O((n+m)*logn) 的，也就是改为用堆维护节点个数，这在一些边很多的稠密图里有作用了。

优化的 Prim 其实很简单，观察整个过程，可以发现会有许多条指向同一个节点的边在堆里，而考虑时却只会考虑权值最小的那条。所以，可以考虑在小根堆里同时维护节点和权值两条信息。对于每次考察的所有边，若去往的点之前考察过了，那么就不用再入堆了。否则，若之前从来没进过堆，那就入堆。若已经进过堆了，那么就手动把这条记录改成两条边权值的最小值，然后再手动调整堆。这样，由于每个节点只会进一次堆出一次堆，所以复杂度就是 O(logn) 的了。

4.Boruvka 算法

Boruvka 算法天然适用于完全图的最小生成树。

Boruvka 算法的思想是，每一轮中，对于当前的每个连通块，都找一条从这个块出去权值最小的边。然后对于所有这些候选边，若能连通两个连通块就选这条边。

定义一张图的 “ 割（cut）” 为将点分为两个集合的方法，那么 Boruvka 算法天然就会形成一个割。此时就有性质：对于任意一个割，权值最小的跨割边必然存在于一个最小生成树上。证明就是，若 e 为一条跨割边连接 (u,v)，对于一棵不包含 e 的最小生成树 T。那么对于 T 中从 u 到 v 这条路径，必然也存在一条跨割边 f。所以就可以删除 f 加入 e，此时形成的树不然不劣于 T，所以仍然是最小生成树。所以这样操作天然可以保证最后得到的是最小生成树。

此时就有结论，每轮连通块数量至少减半，所以最多进行 O(log n) 轮就结束了。这个是因为在每一轮中，每个连通块都会选择一条和其他连通块的边。那么在合并后，每个连通块都不可能还是自己，那么就说明新的连通块至少包含两个旧连通块，所以最后进行 log n 次就结束了。

二、题目

1.买礼物

#include<bits/stdc++.h> using namespace std; vector<int>father; void build(int n) { father.resize(n+1); for(int i=0;i<n;i++) { father[i]=i; } } int find(int i) { if(i!=father[i]) { father[i]=find(father[i]); } return father[i]; } bool Union(int x,int y) { int fx=find(x); int fy=find(y); if(fx!=fy) { father[fx]=fy; return true; } return false; } static bool cmp(vector<int>&a,vector<int>&b) { return a[2]<b[2]; } void solve(int a,int n,int cnt,vector<vector<int>>&edges) { build(cnt); sort(edges.begin(),edges.end(),cmp); int ans=0; for(int i=0;i<cnt;i++) { if(Union(edges[i][0],edges[i][1])) { ans+=edges[i][2]; } } cout<<ans; } void read() { int a,n; cin>>a>>n; vector<vector<int>>edges(n*n+n+1,vector<int>(3)); int cnt=0; for(int i=1;i<=n;i++,cnt++) { edges[cnt][0]=0; edges[cnt][1]=i; edges[cnt][2]=a; } for(int i=0;i<n;i++) { for(int j=0,k;j<n;j++,cnt++) { edges[cnt][0]=i; edges[cnt][1]=j; cin>>k; edges[cnt][2]=k==0?a:k; } } solve(a,n,cnt,edges); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); read(); return 0; }

这个题唯一的难点就在于单独买一个时的处理，略微思考就能想到，只需要加一个零号节点，让其与所有节点相连，其中每条边就是对应节点自己的权重即可。

处理好数据后就是Kruskal的模板了。

2.检查边长度限制的路径是否存在

class Solution { public: vector<int>father; vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) { int m=edgeList.size(); int q=queries.size(); build(n); //记应该填的位置 for(int i=0;i<q;i++) { queries[i].push_back(i); } //根据limit排序 sort(queries.begin(),queries.end(), [&](vector<int>&a,vector<int>&b){return a[2]<b[2];}); //根据边权排序 sort(edgeList.begin(),edgeList.end(), [&](vector<int>&a,vector<int>&b){return a[2]<b[2];}); vector<bool>ans(q); for(int i=0,j=0;i<q;i++) { //合并小于limit的边 for(;j<m&&edgeList[j][2]<queries[i][2];j++) { Union(edgeList[j][0],edgeList[j][1]); } ans[queries[i][3]]=isSameSet(queries[i][0],queries[i][1]); } return ans; } void build(int n) { father.resize(n); for(int i=0;i<n;i++) { father[i]=i; } } void Union(int x,int y) { int fx=find(x); int fy=find(y); if(fx!=fy) { father[fx]=fy; } } int find(int i) { if(i!=father[i]) { father[i]=find(father[i]); } return father[i]; } bool isSameSet(int x,int y) { return find(x)==find(y); } };

这个题就需要一点思考了，由于要求路径上每一条边的权值都小于limit，所以整体思路是，连接所有小于限制的边，生成最小生成树，然后查询要求的两节点是否连通，即在同一集合。

所以考虑先按limit从小到大给查询数组排序，注意为了之后往ans的对应位置输答案，这里要先往每个查询后加入到时候往ans里输的位置。之后遍历每条查询，合并小于limit的边，然后查询是否在同一集合即可。

3.繁忙的都市

#include<bits/stdc++.h> using namespace std; vector<int>father; void build(int n) { father.resize(n+1); for(int i=1;i<=n;i++) { father[i]=i; } } int find(int i) { if(i!=father[i]) { father[i]=find(father[i]); } return father[i]; } bool Union(int x,int y) { int fx=find(x); int fy=find(y); if(fx!=fy) { father[fx]=fy; return true; } return false; } void solve(int n,int m,vector<vector<int>>&edges) { build(n); sort(edges.begin(),edges.end(), [&](vector<int>&a,vector<int>&b){return a[2]<b[2];}); int cnt=0; int Max=0; for(int i=0;i<m;i++) { if(Union(edges[i][0],edges[i][1])) { cnt++; Max=max(Max,edges[i][2]);//最小生成树必是最小瓶颈树 -> 最大边权最小 } if(cnt==n-1)//最小生成树必是n-1条 { break; } } cout<<n-1<<" "<<Max; } void read() { int n,m; cin>>n>>m; vector<vector<int>>edges(m,vector<int>(3)); for(int i=0;i<m;i++) { cin>>edges[i][0]>>edges[i][1]>>edges[i][2]; } solve(n,m,edges); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); read(); return 0; }

这个题有一个结论，就是最小生成树必是最小瓶颈树。最小瓶颈树就是在连通的情况下，要求最大边权最小，即这道题的第三个要求。而有了这个结论之后再思考，可以发现在最小生成树的情况下，这个要求的边数就是n-1。所以只需要统计边的最大值即可。

总结

怎么说呢，最小生成树非常重要。虽然这几个题看上去不是那么吓人，但通常这个还会放在新情境里和其他算法一起出现，那就比较恶心了。

END