前言从图开始的每个算法都挺重要的用途都很广。一、最小生成树1.内容最小生成树是在无向有权图中选择一些边保证所有节点都连通且所有边的总权值最小。2.Kruskal算法——【模板】最小生成树#includebits/stdc.h using namespace std; //并查集 vectorintfather; void build(int n) { father.resize(n1); for(int i1;in;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 fxfind(x); int fyfind(y); if(fx!fy) { father[fx]fy; return true; } else { return false; } } static bool cmp(vectorinta,vectorintb) { return a[2]b[2]; } void solve(int n,int m,vectorvectorintedges) { build(n); //先按边权从小到大排序 sort(edges.begin(),edges.end(),cmp); int ans0; int edgeCnt0; for(int i0;im;i) { if(Union(edges[i][0],edges[i][1])) { edgeCnt; ansedges[i][2]; } } if(edgeCntn-1) { coutans; } else { coutorz; } } void read() { int n,m; cinnm; vectorvectorintedges(m,vectorint(3)); for(int i0;im;i) { cinedges[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#xendl;coutxendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; typedef long long ll; typedef pairint,int pii; typedef pairll,ll pll; const int INF1e9; const ll INFLL1e18; 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 MAXN50005; int n,m; vectorvectorpiig(MAXN); //手写的堆 vectorvectorintheap(MAXN,vectorint(2)); //反向索引表 //-1没入过堆-2弹出过 vectorintwhere(MAXN,-1); int heapSize0; int nodeCnt0; void swap(int i,int j) { int aheap[i][0]; int bheap[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 l1; while(lheapSize) { int bestl1heapSizeheap[l1][1]heap[l][1]?l1:l; bestheap[best][1]heap[i][1]?best:i; if(besti) { break; } swap(best,i); ibest; li*21; } } 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]); } } arrayint,2 pop() { int uheap[0][0]; int wheap[0][1]; swap(0,--heapSize); heapify(0); where[u]-2; nodeCnt; return {u,w}; } int prim() { nodeCnt1; where[1]-2; for(auto [v,w]:g[1]) { add(v,w); } int ans0; while(heapSize) { auto [u,w]pop(); answ; for(auto [v,w]:g[u]) { add(v,w); } } return ans; } void solve() { cinnm; for(int i1,u,v,w;im;i) { cinuvw; g[u].push_back({v,w}); g[v].push_back({u,w}); } int ansprim(); if(nodeCntn) { coutansendl; } else { coutorzendl; } } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; //cint; init(); while(t--) { solve(); } return 0; }先说一下 Prim 算法未优化的过程就是先准备一个集合存当前访问过的点这个可以用一个 vis 数组实现再准备一个小根堆维护所有边。之后随便选一个起始点将这个点标记然后把从这个点连出去的所有边加入小根堆。之后只要堆不为空每次拿出堆顶的边。若这条边指向的节点没访问过那么就要这条边访问这个节点并把这个节点连出去的边都入堆。否则即指向的节点访问过了那么就不要这条边。未优化的 Prim 算法时间复杂度 O(m*logm)。虽然未优化的复杂度和 Kruskal 一样但优化后的 Prim 是可以做到 O(nm)O((nm)*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.买礼物#includebits/stdc.h using namespace std; vectorintfather; void build(int n) { father.resize(n1); for(int i0;in;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 fxfind(x); int fyfind(y); if(fx!fy) { father[fx]fy; return true; } return false; } static bool cmp(vectorinta,vectorintb) { return a[2]b[2]; } void solve(int a,int n,int cnt,vectorvectorintedges) { build(cnt); sort(edges.begin(),edges.end(),cmp); int ans0; for(int i0;icnt;i) { if(Union(edges[i][0],edges[i][1])) { ansedges[i][2]; } } coutans; } void read() { int a,n; cinan; vectorvectorintedges(n*nn1,vectorint(3)); int cnt0; for(int i1;in;i,cnt) { edges[cnt][0]0; edges[cnt][1]i; edges[cnt][2]a; } for(int i0;in;i) { for(int j0,k;jn;j,cnt) { edges[cnt][0]i; edges[cnt][1]j; cink; edges[cnt][2]k0?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: vectorintfather; vectorbool distanceLimitedPathsExist(int n, vectorvectorint edgeList, vectorvectorint queries) { int medgeList.size(); int qqueries.size(); build(n); //记应该填的位置 for(int i0;iq;i) { queries[i].push_back(i); } //根据limit排序 sort(queries.begin(),queries.end(), [](vectorinta,vectorintb){return a[2]b[2];}); //根据边权排序 sort(edgeList.begin(),edgeList.end(), [](vectorinta,vectorintb){return a[2]b[2];}); vectorboolans(q); for(int i0,j0;iq;i) { //合并小于limit的边 for(;jmedgeList[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 i0;in;i) { father[i]i; } } void Union(int x,int y) { int fxfind(x); int fyfind(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.繁忙的都市#includebits/stdc.h using namespace std; vectorintfather; void build(int n) { father.resize(n1); for(int i1;in;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 fxfind(x); int fyfind(y); if(fx!fy) { father[fx]fy; return true; } return false; } void solve(int n,int m,vectorvectorintedges) { build(n); sort(edges.begin(),edges.end(), [](vectorinta,vectorintb){return a[2]b[2];}); int cnt0; int Max0; for(int i0;im;i) { if(Union(edges[i][0],edges[i][1])) { cnt; Maxmax(Max,edges[i][2]);//最小生成树必是最小瓶颈树 - 最大边权最小 } if(cntn-1)//最小生成树必是n-1条 { break; } } coutn-1 Max; } void read() { int n,m; cinnm; vectorvectorintedges(m,vectorint(3)); for(int i0;im;i) { cinedges[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