锐客网

  1. 首页 > it技术 > >

图论|【图论-最小生成树】洛谷官方题单刷题总结

算法图论

#最小生成树
无向图 G=(V,E) n个顶点，m条边 使用图中有的边，将所有顶点连起来（n个顶点，则需要n-1条边)这个子图称为生成树，而使用的边的权值之和最小的子图称为最小生成树。
kruskal 算法（加边法） step1.将所有的边按照权值排序（生成树中的两个端点或者两个连通分量之间，一定是通过存在且权值最小的边相连）
图论|【图论-最小生成树】洛谷官方题单刷题总结
文章图片
**step2** 所有的点作为单独的集合（一个点是一个集合）（并查集初始化） **step3** 将通过边连接各集合，最终的生成树即所有点都在一个集合中。选择加入新的边（已排序即最优的），如果该边连接的两个端点不再一个集合中（并查集判别），加入该条边，并将两个集合合并（并查集合并）。 洛谷-最小生成树模板
P1546 [USACO3.1]最短网络 Agri-Net
以邻接矩阵的形式给出图，求解最小生成树代价。kruskal和prime算法都可以。

#include using namespace std; #define Maxx 10010 int N,ans,cnt,val,x,y; int p[Maxx]; struct Node{ int x,y,val; }a[Maxx]; bool cmp(Node n1,Node n2){ return n1.val>N; for(int i=1; i<=N; i++){ for(int j=1; j<=N; j++){ cin>>val; if(val!=0) a[++cnt]={i,j,val}; } } kruskal(); cout<

洛谷_USACO_Building_Roads_S 连通最小代价
题目描述
在坐标系中的n 坐标(,x,y)个点，给出m条边连接(i,j)，边的长度等于在坐标系中的距离。问添加最小的边的长度，使所有点连通。
题目思路
最小生成树具有连通且需花费权值最小的性质。对于已经加入的边(m条已有的边），花费就是0了，然后枚举任意两个点，可得到一个完全图，然后用kruskal计算最小生成树的代价。
Code
#include using namespace std; #define N 500010 struct Node{ int x,y; double val; }; Node a[N],b[N]; int n,m,x,y,w,cnt; double sum; int p[5100]; bool cmp(Node n1,Node n2){ return n1.val>n>>m; for(int i=1; i<=n; i++){ cin>>b[i].x>>b[i].y; } init(); for(int i=1; i<=m; i++){ cin>>x>>y; int px=findP(x),py=findP(y); p[px]=py; } for(int i=1; i<=n; i++){ for(int j=i+1; j<=n; j++){ a[++cnt].x=i; a[cnt].y=j; double dx=1.0*(b[i].x-b[j].x); double dy=1.0*(b[i].y-b[j].y); a[cnt].val=sqrt(dx*dx+dy*dy); } } sort(a+1,a+1+cnt,cmp); kruskal(); printf("%.2f",sum); }

prim算法（加点法） prim算法类似于dijkstra算法,
step1.将1号结点加入生成树集合T，其余为生成树集合S，用数组D[i]标记集合S任意点到集合T中i的最小距离，vis[x] 标记顶点x是否在生成树集合S中。（初始D[i]=G[1,i] vis[1]=1 vis[其余]=0)
step2.每次从D[i]中寻找最小值且未在集合S中的顶点i，更新D[j] i与j 有边相连 (D[j]=min(D[i],G[i][j])) ，直到所有顶点都加入生成树集合S中。
堆优化的prim算法实现模板题
#include using namespace std; #define NUM 5100 int n,m,k,x,y,z,ans,cnt; int vis[NUM],d[NUM]; //prim算法数据结构，vis数组(是否加入生成树集合) d数组距离(选择最优) priority_queue< pair >q; //大根堆，使用负数变为小根堆，第一维为-d[i],第二位i int head[NUM],next_[400005],ver[400005],edge[400005],tot; //数组模拟邻接表 //注意点!!! M≤2×10^5 因为是双向边存储所以边的数目必须是这个数据的二倍 void add(int x,int y ,int z){ ver[++tot]=y; edge[tot]=z; next_[tot]=head[x]; head[x]=tot; } void prim(){ //如果多组数据不要忘了初始化，memset可能会超时可以选择循环赋值 memset(d,0x3f,sizeof(d)); d[1]=0; q.push(make_pair(0,1)); while(!q.empty()&&cntz){ d[y]=z; q.push(make_pair(-d[y],y)); } } } } int main() {scanf("%d%d",&n,&m); for(int i=1; i<=m; i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); //无向边加上相反边 } prim(); if(cnt==n) cout<

洛谷_P1991_无线通讯网
题目描述
坐标系内有n个哨所，哨所之间通信需要通信设备，有两种通信设备可供使用，
1.两个哨所都安装了卫星通信，可以实现0距离花费通信。
2.安装有线设备，这种设备最大只能D距离通信。因为设备标准需要统一，所以所有有线设备的最大通信距离相同。
现在要使所有哨所都能够通过某种方式直接或者间接的通信，给出可以安装卫星通信的设备数量，数量不足需要安装有线设备，问有线设备的通信距离D是多少？
解题思路
使所有哨所连通，生成树？根据题目，考虑相关因素，卫星通信不占用且不需要任何有线的花费，所以s个卫星设备可将s个哨所无花费相连。剩余n-s(设哨所集合A) 与s(设哨所集合B) ，需要通过有线设备连通A,同时需要线路连通A与B。计算出花费最大值，就是答案了。
#include using namespace std; #define N 510 int s,n,v[N],x,y,w; double d[N],g[N][N],cost[N]; //cost加入点i的花销 paira[N]; //保存个哨所坐标 priority_queue >heap; void prim(){//只需加入n-s+1个点，不如将加入的n-1个点的权值放在数组中，排序取后n-s个小的 for(int i=1; i<=n; i++) d[i]=100100; //不要忘记初始化哦 d[1]=0; heap.push(make_pair(0,1)); while(!heap.empty()){ x=heap.top().second; heap.pop(); if(v[x]) continue; v[x]=1; cost[x]=d[x]; //cout<g[x][i]){ d[i]=g[x][i]; heap.push(make_pair(-d[i],i)); } } } //for(int i=1; i<=n; i++) cout<>s>>n; for(int i=1; i<=n; i++) cin>>a[i].first>>a[i].second; if(s>=n){ cout<<0<

【图论|【图论-最小生成树】洛谷官方题单刷题总结】已经结束了，只能走到这了（时间：2022/3/22 5:25 确实*25达不到）。或许能力有限，或许努力不足。
计划的还没做完，短期内没有任何意义了。
仿佛陷入循环，咫尺之距，遥不可及。
给自己一个缓冲，4.15后，之后再见，会回来的。

    推荐阅读


    上一篇：repeat_全球变暖_DFS

    下一篇：C++|C++(八股文) —— 指针和引用的区别