长宁区网站建设公,自己怎么做微网站,界面设计器,网站定位分析是什么1.Kruskal算法概念以及基本思路
#xff08;1#xff09;概念#xff1a;
克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。它的时间复杂度为O#xff08;ElogE#xff09;(E是图G的边的总数)#xff0c;适合于求边稀疏的网的最小生成树 。
其基本思想是#xff…1.Kruskal算法概念以及基本思路
1概念
克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。它的时间复杂度为OElogE(E是图G的边的总数)适合于求边稀疏的网的最小生成树 。
其基本思想是假设连通网G令最小生成树的初始状态为只有n个顶点且没有任何一条边的图T概述图中每个顶点自成一个连通分量。在E中选择代价最小即距离最短的边若该边依附的顶点分别在T中不同的连通分量上则将此边加入到T中否则舍去此边而选择下一条代价最小的边。换而言之就是在整个图找最短的边从短到长一次寻找若没有连通则进行连通若已经连通则放弃这个边去寻找下一个知道变成连通图
2基本思路
从它的基本思想我们可以得出做题时的基本思路
1.首先创建一个一维数组用于判断这个点是否连通每个数组的初始值都对应自己的下标
2.创建一个结构体存储位置信息以及之间的长度
3.通过快排进行排序将路径最短的排在前面
4.根据题解去寻找最小生成树
2.相关例题
第一题最小生成树 题解这题就是最基本的最小生成树问题没有什么难度
#includebits/stdc.h
using namespace std;int n,m;//n个结点和m条边
struct lu//代表路径的结构体
{int start;//起始节点int end1;//终止结点int l;//路径长度
}q[200005];
int f[50005];//用于判断是否连通的数组
int count1;//统计已经连通几条边
long long sum;//总长度int cha(int x)//查判断是否属于同一个根节点
{if(f[x]x)return x;return cha(f[x]);
}void bing(int root1,int root2)//并将根节点并在一起
{if(root1root2)return;f[root2]root1;
}bool cmp(lu a,lu b)//路径要根据路径长度进行比较
{return a.lb.l;//快排顺序从小到大排列路径长度
}int main()
{scanf(%d%d,n,m);for(int i1;in;i){f[i]i;//将根节点设置为自己}for(int i0;im;i){scanf(%d%d%d,q[i].start,q[i].end1,q[i].l);}sort(q1,qm1,cmp);//快排for(int i0;im;i){if(cha(q[i].start)cha(q[i].end1))//如果已经并在一起就直接跳过continue;bing(cha(q[i].start),cha(q[i].end1));sumq[i].l;count1;if(count1n-1)//当满足了连通图这个是连通图的性质边数顶点数-1break;}if(count1n-1)//如果是非连通图{printf(orz);return 0;}printf(%d,sum);return 0;
}
第二题拆地毯 题解这题其实就是最小生成树的地方略变一点儿求的是最大生成树我们要找的是最长的长度那么我们只需要改变一下快排的方式即可
AC代码
#includebits/stdc.h
using namespace std;
int n,m,k;
struct lu
{int start;int end1;int l;
}q[100005];
int f[100005];
int count1;
int sum;
int cha(int x)
{if(f[x]x)return x;return cha(f[x]);
}
void bing(int root1,int root2)
{if(root1root2)return ;f[root2]root1;
}
bool cmp(lu a,lu b)
{return a.lb.l;//改变一下快排的方式
}
int main()
{scanf(%d%d%d,n,m,k);for(int i1;in;i)f[i]i;for(int i0;im;i){scanf(%d%d%d,q[i].start,q[i].end1,q[i].l);}sort(q,qm,cmp);for(int i0;im;i){if(cha(q[i].start)cha(q[i].end1))continue;bing(cha(q[i].start),cha(q[i].end1));count1;sumq[i].l;if(count1k)//当保留的地毯满足保留的个数结束就可以break;}printf(%d,sum);return 0;
}
第三题无线通讯网 题解也是最小生成树类的题目但是没什么的唯一改变的地方就是因为这个地方不是求路径和而是卡的最小的无线电所需要的距离也就是卡的极限最小值
#includebits/stdc.h
using namespace std;
int s,p;
int x[505],y[505];
int f[1000005];
struct lu
{int start;int end1;double l;
}q[2000005];
int count1;
double sum;
int cha(int x)
{if(f[x]x)return x;return cha(f[x]);
}
void bing(int root1,int root2)
{if(root1root2)return ;f[root2]root1;
}
bool cmp(lu a,lu b)
{return a.lb.l;
}
int main()
{int flag0;scanf(%d%d,s,p);for(int i1;ip;i)f[i]i;for(int i1;ip;i){scanf(%d%d,x[i],y[i]);for(int j1;ji;j){flag;q[flag].starti;q[flag].end1j;q[flag].lsqrt((x[i]-x[j])*(x[i]-x[j])(y[i]-y[j])*(y[i]-y[j]));}}sort(q1,q1flag,cmp);for(int i1;iflag;i){if(cha(q[i].start)cha(q[i].end1))continue;sumq[i].l;//长度就是那个极限的值bing(cha(q[i].start),cha(q[i].end1));count1;if(count1p-s)//当满足了结束条件break;}printf(%.2lf,sum);return 0;
}
第四题营救 题解也是最小生成树的题目和第三题其实一样只不过排的是拥挤度
AC代码
#includebits/stdc.h
using namespace std;
int n,m,s,t;
struct lu
{int start;int end1;int l;
}q[20005];
int f[10005];
int count1;
int sum;
int cha(int x)
{if(f[x]x)return x;return cha(f[x]);
}
void bing(int root1,int root2)
{if(root1root2)return ;f[root2]root1;
}
bool cmp(lu a,lu b)
{return a.lb.l;
}
int main()
{scanf(%d%d%d%d,n,m,s,t);for(int i1;in;i)f[i]i;for(int i0;im;i){scanf(%d%d%d,q[i].start,q[i].end1,q[i].l);}sort(q,qm,cmp);for(int i0;im;i){bing(cha(q[i].start),cha(q[i].end1));sumq[i].l;if(cha(s)cha(t)){break;}}printf(%d,sum);return 0;
}
第五题买礼物 题解这题有一个坑就是有可能绑定在一起买比单个买还要贵因此我们在进行价值的计算时需要有一个判断
#includebits/stdc.h
using namespace std;
int a,b;
struct wu
{int x,y;int w;
}q[250005];
int f[505];
int sum;
int count1;
int cha(int x)
{if(f[x]x)return x;return cha(f[x]);
}
void bing(int root1,int root2)
{if(root1root2){return ;}f[root2]root1;
}
bool cmp(wu a,wu b)
{return a.wb.w;
}
int main()
{scanf(%d%d,a,b);suma;for(int i1;ib;i)f[i]i;for(int i1;ib;i){for(int j1;jb;j){count1;scanf(%d,q[count1].w);q[count1].xi;q[count1].yj;if(q[count1].w0)q[count1].wa;}}sort(q1,q1count1,cmp);for(int i1;icount1;i){if(cha(q[i].x)cha(q[i].y))continue;bing(cha(q[i].x),cha(q[i].y));summin(q[i].w,a);//去优惠价格和原价格的小值}printf(%d,sum);return 0;
} 第六题Building Roads S 题解这题也是很简单的和无线电那个在处理坐标的方式差不多但是恶心的地方在于精度的把控需要在原本的精度上更加细致不然还是会WA血的教训也是一开始就中计了啊大意了没有闪
