搜索
连接所有点的最小费用给你一个points数组,表示2D平面上的一些点,其中points[i][xi,yi]。连接点[xi,yi]和点[xj,yj]的费用为它们之间的曼哈顿距离:|xixj|+|yiyj
2022-05-18
NOIP2013货车运输题目描述A国有n座城市,编号从1到n,城市之间有m条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有q辆货车在运输货物,司机们想知道每辆车在不超过车辆限重的情况下,最多
2022-05-05
OJ题号:BZOJ1016题目大意:给定一个无向带权图,求最小生成树的个数。思路:先跑一遍最小生成树,统计相同权值的边出现的个数。易证不同的最小生成树,它们不同的那一部分边的权值实际上是相同的。所以我
2022-04-20
思路:考虑使用卫星替代最小生成树中最大的$s1$条边,答案即为剩下的最大边。1include<cmath>2include<cstdio>3include<cctype&
2022-04-20
OJ题号:BZOJ4242、AtCoderJOISC2014E题目大意:给你一个h*w的网格图,每个格子可能是空地、障碍物和建筑物。你只可以从空地上走过或者从建筑物中穿过。建筑物总共有p个,现在有q组
2022-04-20
随着如今社会的不断变化,交通问题也变得越来越重要,所以市长决定建设一些公路来方便各个城市之间的贸易和交易。虽然市长的想法很好,但是他也遇到了一般人也经常头疼的问题,那就是手头的经费有限……在规划过程中
2022-04-20
OJ题号:BZOJ1977、COGS2453题目大意:给你一个无向连通图,求严格次小生成树。思路:对于一般次小生成树,我们有一个结论:一般次小生成树一定可以通过替换掉最小生成树某一条边得到。因此对于一
2022-04-20
2328:Star时间限制:C/C++1sJava/Python3s内存限制:128MB答案正确:9提交:26题目描述31世纪,人类世界的科技已经发展到了空前的高度,星际移民,星际旅游早已经不再是问题
2022-04-20
OJ题号:BZOJ1083、洛谷2330思路:Kruskal。1include<cstdio>2include<utility>3include<algorithm>
2022-04-19
OJ题号:POJ1258、洛谷1546思路:Kruskal。1include<cstdio>2include<utility>3include<vector>4in
2022-04-17
思路:Kruskal1include<cstdio>2include<utility>3include<algorithm>4definewfirst5define
2022-04-16
orz,感觉对最小生成树的理解又加进了一步。ps:不得不说对于经典算法的探究是永无止境的,只能通过交流和增长见识来学习和体会,自己研究确实困难。让我们来深入分析一下kruskal算法。算法过程不多说,
2022-04-15
传送门解题思路两种方法:方法一:直接按照Kruskal的方法求最小生成树,求的过程中s和t刚刚联通时加的边的大小即为答案。方法二:先二分答案,然后跑一遍最短路,要求只能走边权小于二分值的边。AC代码i
2022-04-14
传送门解题思路和上一道题基本相同。但是这个题题面是真的复杂,读了好久才读懂。关键在于如何建图。将在第0列可以看做第0个点,第n列可以看做第m+1个点。这两个特殊的点到其他点的距离为点线垂直距离,其他的
2022-04-13
【算法】最大生成树+LCA(倍增)【题解】两点间选择一条路径最小值最大的路径,这条路径一定在最大生成树上,因为最大生成树就是从边权最大的边开始加的。先求原图的最大生成树(森林),重新构图,然后用一个超
2022-04-09
[BZOJ2238]Mst题目大意:给你一个\(n(n\le50000)\)个点,\(m(m\le10^5)\)条边的无向带权图。\(q(q\le10^5)\)次询问,每次询问去掉一条边后图能否连通,
2022-04-09
【算法】最小生成树include<cstdio>include<algorithm>usingnamespacestd;constintmaxn310;structcyc{in
2022-04-08
[BZOJ3080]MinimumVarianceSpanningTree/[BZOJ3754]Tree之最小方差树题目大意:给定一个\(n(n\le50)\)个点,\(m(m\le1000)\)条边
2022-04-08
目录定义带权图的实现Kruskal算法二叉堆并查集实现算法Prim算法定义在一幅无向图G(V,E)中,(u,v)为连接顶点u和顶点v的边,w(u,v)为边的权重,若存在边的子集TE且(V,T)为树,使
2022-04-07
[BZOJ2654]Tree题目来源:[BZOJ2654]Tree[HDU4253]TwoFamousCompanies[SPOJCOMPANYS]TwoFamousCompanies题目大意:一个\
2022-04-01