BZOJ 3714: [PA2014]Kuglarz Kruskal

题目能转化成最小生成树,挺神奇的。想了半天没想出来。

用sum[i]表示前i个杯子底球的总数,知道一个c[i][j],等于是知道了sum[j]和sum[i-1]的差的奇偶性。而sum[0]是知道的,所以只需要知道所有sum[i]与sum[0]的差的奇偶性,我们一位一位向前推,就可以推出每个杯子[……]

Read more

BZOJ 2429: [HAOI2006]聪明的猴子 Kruskal

这题实在是太简单了,求生成树上的最大边就行了,直接上网贴了份代码交上去了。

但是通过这道题学到了一个新的名词(思想? 最小瓶颈生成树。大概就是最大边要最小,而Kruskal算法求出的就是最小瓶颈生成树。

BZOJ 1821: [JSOI2010]Group 部落划分 Group 并查集 贪心 二分

我们把所有边排个序,然后从大到小选,并查集维护连联通性,然后选入n – k条边之后,就形成了k个联通块,剩下边中可以选的最大值就是所求的答案。一定要注意是剩下边中可以选择的,也就是连接两个联通块的边的长度才是答案,开始直接输出的下一条边的值,这个答案可能偏小,因为它可能位于联通块内。

还有一种[……]

Read more

BZOJ 1601: [Usaco2008 Oct]灌水 最小生成树

建一个超级源,到每个点连w[i],求最小生成树即可

BZOJ1016 [JSOI2008]最小生成树计数 代码重构

整理板子实在看不下去之前的代码,重构了一下。

bzoj 2753: [SCOI2012]滑雪与时间胶囊 kruskal

看复杂度就不是最小树形图。显然是MST魔改以下。这个图相当于很大一部分是有向边,有一些小部分是无向边。按照从上(1号点高度)向下的顺序来,自然也就保证了正确性,保证了每次是从1号点的联通快连出去,用MST处理就行了,

以下为正解;

第一个问宽搜解决。

第二个问,按照第一关键字有向边[……]

Read more

bzoj 3732: Network 倍增lca kruscal

倍增lca里面注意返回值前上爬的最后一步,不要忘了。还有不要把数组名写混了。

在最小生成树上跑倍增lca即可。

bzoj 2654: tree 二分 kruscal

看到这道题感觉毫无想法,然后有羞耻的查了题解。话说最近查了好多题解。感觉药丸。

我们考虑一下用kruscal算法求MST的时候,如果选的白边不够,那么我们尝试让白边边权集体变小,则必定可以使得白边数量满足。如果白边选的太多,我们尝试让白边集体变大,则必定可以使白边数量变小。这实际上是可以二分的[……]

Read more

bzoj 1016: [JSOI2008]最小生成树计数

这是一道kruskal和dfs的题。我们根据题意可以得出一些结论,只有边权相等的一些边,在这些边中选出一些可以达到的效果,可以被这些边中的另外一个子集达到同样的效果。想一下kruskal,这个非常显然。这样子我们可以先进行一遍kruskal,来求出每种边权选择几条。最后将哪些点联通。然后我们对于这种[……]

Read more