Day1:A+组

【元素】
题意:将n个整数分组,使组数最少且元素最多的组的元素个数尽量少。
数据范围给出提示,n<=15,符合这个范围的算法有深搜、状压DP。这里考虑深搜,枚举组数N,对于每一个数枚举其所在的组。时间复杂度为O(刚好能过)。
状压DP时间复杂度较为严谨,为O(2 ^ n * n ^ 2)。 令f[i]为状态i时最少需要的组数,对于两个状态opt、nav。若能合并,则f[opt ^ nav] = min(f[opt], f[nav])。若不能合并,则需讨论。

【反击】
题意:在n个数中找出最多满足条件的完美对数。
n <= 1000,可以暴力判断每两个数是否能符合条件,由于不能重复选取,联想到二分图。二分图求最大匹配方法有许多,这里使用网络流求二分图。将每个点拆成两点,每个点与另一边能与自己匹配的点连一条流量上限为1的边。源点s与一半的点连边,流量上限为正无穷。汇点t与另一半的点连边,流量上限为正无穷。
时间复杂度为O(nlogn).

【最小】
题意:将n点m边图中的点分为白点和黑点。 删除一些边,使剩下的边代价尽量小,且白点与最近的黑点仍按原先的最短路连接。
答案要求按最短路连接,于是先删除不在最短路上的边,再求最小生成树。最短路用spfa求解,由于有多个源点,先将所有黑点入队再求最短路。删边后只需满足白点与黑点由最短路连接,因此可能出现删边后成为森林的现象,在求最小生成树是将所有黑点先行合并。

主要代码如下

继续阅读Day1:A+组

[BZOJ 3624] [APIO 2008] 免费道路

并查集。

题意:求把 N 个点用 N-1 条边连成一棵树,且其中恰有 K 条边为 0 边的一种方案。

第一反应:先连 0 边再连 1 边。

但可能会有这么一种情况:所有的 1 边都连上之后仍然整个图仍然是不联通的。这意味着有一些 0 边是必选的。但如果像上面那样直接做的话可能选不到这些边,从而得不出答案。

于是可以这样做:

先把所有 1 边端点合并,然后接着枚举 0 边,若两顶点不在同一集合中,则把这条边端点所在集合合并,并加入答案中。

接着把并查集重置成只有答案集合中的边的情况,加入能加的 0 边直到答案中的 0 边数量达到 K。最后加入 1 边。

这题还要判断方案是否存在,判断方法为 1. 选取的 0 边边数恰为 K。 2. 选取的总边数为 N-1

代码如下(BZOJ 有点诡异,endl 交上去会 RTE,而 '\n' 就没问题):

继续阅读[BZOJ 3624] [APIO 2008] 免费道路

[BZOJ 4031] [HEOI 2015] 小Z的房间

Kirchhoff's theorem or Kirchhoff's matrix tree theorem

  1. G的度数矩阵DG是一个n*n的矩阵,并且满足:当i≠j时,Di,j=0;当i=j时,Di,j等于Vi的度数。
  2. G的邻接矩阵AG也是一个n*n的矩阵,并且满足:如果ViVj之间有边直接相连,则Ai,j=1,否则为0。

定义G的 Kirchhoff 矩阵CGCG=DGAG

Matrix-Tree 定理:G的所有不同的生成树的个数等于其 Kirchhoff 矩阵 CG任何一个n-1阶主子式(去掉第行第i列的新矩阵)的行列式的绝对值。

运用高斯消元计算行列式绝对值。高斯消元过程中除法运用辗转相消实现。

Reference:

https://www.cnblogs.com/wuyuhan/p/5238652.html

https://www.cnblogs.com/GerynOhenz/p/4450417.html

http://blog.csdn.net/u010182633/article/details/45225179

代码如下:

继续阅读[BZOJ 4031] [HEOI 2015] 小Z的房间

【BZOJ3624】免费道路

这题大意是有n个点, 给你m条边,其中有一些是水泥路,另一些是鹅卵石路。让你取n-1条边,其中要有k条鹅卵石路,使它成为一棵生成树。

因为有两种路,所以肯定要有几条边是一定要取得,那就先将所有水泥路连边,接着再做生成树,则需要加的边肯定是在答案中的。

这时再判断必定要取的鹅卵石路是否大于k,若大于k则无答案。接着只要将剩下的点做生成树即可