Deep_Kevin的娱乐空间

正题      第一题：最短网络 Agri-Net      这题没有什么好说的，就是p算法跑一次即可。代码#include<cstdio> #include<cstdlib> #include<cstring> #include<queue> using namespace std; struct edge{ int x,y,c,next; ...

正题      第二题：[SCOI2005]繁忙的都市      这题十分的明显，就是求边权最大的最小值，而最小生成树又可以满足这个性质。      所以就是跑一边最小生成树即可。代码#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using names...

正题      第三题：无线通讯网      这题中的卫星电话，就指的是可以把原图分成S个联通块后，就可以互相联通。      那我们要把原图分成S个联通块，那么我们只需要选中P-S条最短的边（当然是不联通的两个点）。      然后输出最大边最小即可，那么想到了最大边最小，我们就想到了最小生成树，选S-P条边即可。代码<我是二分的，太菜了>#include<cstdio>...

正文      第六题：牛的旅行 Cow Tours      这题看上去好像很烦，其实题意就是说有很多个点，被分成若干个联通块，图中有边，定义一个图的直径是最远两个点的路径长度。所以很明显了，我们只要算出一个点到当前联通块其他点的最长路径。就可以暴力枚举不同联通块的每个点，算出距离加上前面预处理好的那个到当前联通块的最长路，更新min即可。      最后还要判断原来集合的直径是否比现在的集合还...

正题      第四题：公路修建      这道题的第二个说明是用来误导你的，因为它是一个等边三角形，很容易就可以知道了。      另外我们来讨论数据范围，n是5000，又因为它是一张完全图。所以边数就有25000000条。那么如果我们用n的平方的prim算法，就可以卡过所有的数据点了。（用堆优化不行，因为复杂度是mlogn，很大）代码<注意变量名的使用>// luogu-judge...

正题       第一题：货车运输       这道题很经典啊~~       直接建立倍增关系式求LCA即可。       不妨设i的第2^j个爸爸是f[i][j],而这条路径上的最小值设为mmin[i][j]。       f[i][j]=f[f[i][j-1](i的2^(j-1)次方爸爸)][j-1]的第j-1次方个爸爸。       那么mmin[i][j]=min(mmin[i][j-1...

正题 “诶，今天讲最小生成树哎。不听了，我刷我自己的题。。”------来自某位神犇。 太难了。 求解最小生成树有两种方法Kruskal和Prim算法，图较为稀疏的情况下，我们一般选择前者。图较为稠密的情况下，我们一般选择后者。 只讲一些我原先不懂得例题。（即使我懂的也就那几道。。。 例题1：动态图连通性 给定一个...