BZOJ1016 | JSOI2008 最小生成树计数

题面不放

这是道好题 一开始还以为是\rm{Matrix Tree}定理,后来发现不是QAQ

其实暴搜可过

先一遍Kruskal,顺便把权值相等的边们分到一个块里面,随便怎么实现都行 记录一下每个块有多少边在MST中出现过

然后重置一下并查集,枚举块,每个块跑DFS选哪些边(注意连通性,如果这条边加入成环就不能选,这很显然qwq),答案是所有块的方案数的乘积。

这里用了一个性质就是不同的MST中边权相等的边出现次数相等,证明?

开始时,每个点单独构成一个集合。

首先只考虑权值最小的边,将它们全部添加进图中,并去掉环,由于是全部尝试添加,那么只要是用这种权值的边能够连通的点,最终就一定能在一个集合中。

那么不管添加的是哪些边,最终形成的集合数都是一定的,且集合的划分情况一定相同。那么真正添加的边数也是相同的。因为每添加一条边集合的数目便减少1.

那么权值第二小的边呢?我们将之间得到的集合每个集合都缩为一个点,那么权值第二小的边就变成了当前权值最小的边,也有上述的结论。

因此每个阶段,添加的边数都是相同的。我们以权值划分阶段,那么也就意味着某种权值的边的数目是完全相同的。

上文不是我写的。引用一下。

然后就能愉快的切掉这个水题。

 

点击图片跳转原题

 

 

 

 

 

哦,还有,这段代码BZOJ编译会CE,不知道为什么她就是不支持C++11   [摊手]

 

#洛谷P1967 货车运输

题目描述

A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物, 司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。

输入输出格式

输入格式:

输入文件名为 truck.in。

输入文件第一行有两个用一个空格隔开的整数 n,m,表示 A 国有 n 座城市和 m 条道

路。 接下来 m 行每行 3 个整数 x、 y、 z,每两个整数之间用一个空格隔开,表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意: x 不等于 y,两座城市之间可能有多条道路 

接下来一行有一个整数 q,表示有 q 辆货车需要运货。

接下来 q 行,每行两个整数 x、y,之间用一个空格隔开,表示一辆货车需要从 x 城市运输货物到 y 城市,注意: x 不等于 y 

输出格式:

输出文件名为 truck.out。

输出共有 q 行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。如果货

车不能到达目的地,输出-1。

先Kruskal跑一下最大生成树,就是把边权改成从大到小排序就行。

然后用倍增思想在有根树上记录一个minp[i][k]数组,表示这个点i上跳2k的高度,经过路径的最小边权:

显然它等于minp[i][k-1]和minp[l[i][k-1][k-1]中的最小值。也就是它向上跳2k-1高度的minp和从depth[i]-2k-1高度再往上跳2k-1高度的minp(参照倍增的思想)

而向上跳2k-1高度能够达到点l[i][k-1],这个就属于LCA的基本操作了吧……

注意初始化。

还要维护一下点的联通行……用Kruskal留下来的UFS就行。

[SCOI2005]繁忙的都市

城市C是一个非常繁忙的大都市,城市中的道路十分的拥挤,于是市长决定对其中的道路进行改造。城市C的道路是这样分布的:城市中有n个交叉路口,有些交叉路口之间有道路相连,两个交叉路口之间最多有一条道路相连接。这些道路是双向的,且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值,分值越小表示这个道路越繁忙,越需要进行改造。但是市政府的资金有限,市长希望进行改造的道路越少越好,于是他提出下面的要求:

1.改造的那些道路能够把所有的交叉路口直接或间接的连通起来。

2.在满足要求1的情况下,改造的道路尽量少。

3.在满足要求1、2的情况下,改造的那些道路中分值最大的道路分值尽量小。

任务:作为市规划局的你,应当作出最佳的决策,选择那些道路应当被修建。

大意就是用最小的代价把N个点的图变成连通图(要求1、2)

那么,N个点的联通图最小需要N-1条边,这显然是一个MST的题。

根据要求3,显然使用并查集维护的Kruskal更优。

那这就是个MST的裸题了……QnQ这么简单为什么还要发题解

关于s,可以知道它肯定是N-1 (N是点数)