关于 Purfer 序列

随便抄点什么玩意当笔记用

purfer 序列是啥就不说了

构造方法

不断选取树上编号最小的叶子删除,并加入序列的末尾。

还原方法

\mathbb{A} = \{ 1, 2, 3, \cdots , n \} 以及 purfer 序列 \{ a_i \}

\mathbb{A} 是所谓的度数序列,初始值全是 1 ,然后 Purfer 序列里每个数字都对 \mathbb{A} 1 的贡献。

顺次取出 Purfer  的首个元素,并在 \mathbb{A} 中选择最小的度数为 1 的元素与之连边。

之后这两个元素的度数均 -1

最后 \mathbb{A} 中应该还剩两个元素,将它们连边。

一个性质

因为要进入 purfer 序列就必须要成为一个叶子,那么也就是说 (对于原数的非叶节点) 每个节点在 purfer 序列中出现了它的度数 -1 这么多次 (有一个临点要当父亲) 

(HNOI2008)

从特殊的图论模型谈开去

最近停课集训算是让我短时间内也接触了不少图论模型,再加上之前的,够我写一篇文了。

在这篇里面我并不想谈关于 弦图,区间图,PQTree,完美消除序列 以及那篇文留下的几个大坑,我想从几个比较常用的和比较具有启发性的小玩意说起。

 

 

 

 

 

 

 

 

斯坦纳树

我是在做 [JLOI2015]管道连接 的时候学习到 Steiner Tree Problem 的。这个东西是什么呢?

我们看一下背景……


背景

Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a number of settings, they all require an optimal interconnect for a given set of objects and a predefined objective function. One well-known variant, which is often used synonymously with the term Steiner tree problem, is the Steiner tree problem in graphs. Given an undirected graph with non-negative edge weights and a subset of vertices, usually referred to as terminals, the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals (but may include additional vertices). Further well-known variants are the Euclidean Steiner tree problem and the rectilinear minimum Steiner tree problem.


斯坦纳树问题 (STP) , 或者说最小斯坦纳树问题, 是一类 组合优化 问题的统称, 那么尽管这个问题可能被设定到许多环境中, 但它都是一类要求: 对于给定的一个对象集合和一个预先定义好的作用于对象的函数, 求出集合的最佳互联的问题.

我们常用的 Steiner Tree Problem 的一个同义指的是在上的 STP . 也就是给定一个非负权边的无向图 和一个顶点的子集 ( 这些给定的顶点通常被称为 terminals ) , 那么我们要求一个把 terminals 联通的最小权生成树. (虽然这个生成树可以有非 terminal 结点).

还有一些奇怪的变种比如 Euclidean Steiner tree problem 和 rectilinear minimum Steiner tree problem.

(这个翻译我真的尽力了.)(我再翻译一些)

这个问题可以说是(非负权的)最短路问题和 MST 问题的组合. 那么如果只有两个 terminals , 它显然是一个最短路问题. 如果所有的结点都是 terminals , 它则是一个 MST 问题.

虽然最短路问题和 MST 问题都是 P 问题, 他们的好哥们 Steiner Tree Problem 却是一个 NPC 问题! 但是虽然大多数 STP 都是 NP-hard 的, 但在某些限制条件下它可以在多项式时间内解决.


PollakGilber猜想

Pollak-Gilbert 猜想指出,平面上任意 n 点集,斯坦纳最小树长与最小生成树之长的比值的最小值是 \frac{\sqrt{3}}{2}


求解问题

子集DP。把 j 的二进制各位的 0/1 看做集合中各个元素选/不选,那么可以设计状态 dp[i][j] 来表示以 i 作为根, 并且集合选择状态为 j 的情况下的最优解答。

转移分两步:

  • 先通过对 j 进行划分求得对于 i,j 下的最优解。
  • 再通过 i,j 去优化 j 下的其他根的答案。

为什么只优化 j 下的呢?因为其他联通状态会转移到 j 或由 j 转移得到。

第一种转移:

除了枚举子集去更新之外,不要忘记要把有效状态放入队列。

第二种转移:


复杂度分析

我们枚举子集的复杂度应是 n \times \sum (C_k^i \times 2^i) = n \times 3^k

那个 SPFA 的复杂度是 n \times 2^k

那么就是 O(n \times 3^k)


流程回顾


Advanced: 斯坦纳森林问题

并没有多大难度。

考虑这样一件事情:我们给定并非一组 terminals ,我们给定 k 组。

对于这 k 组 terminals ,我们只要求同组中的是互相联通的。求一个生成树的最小花费方案。

那么我们可以这样:

我们枚举一个状态 w , 然后我们把 w 二进制拆分对应的几个集合中的 terminals 看成一组 terminals 。然后去做 STP。

然后我们求全集的答案就是再次子集DP一遍:

就很简单做完了。


图的遍历问题

这个问题比较有来头,他牵涉到了图论的起源(或者说创生?)

背景是著名的所谓 Könisberg seven bridge problem ,相信大家都已经耳熟能详了。

由此我们诞生了 Euler 回路或者说, Euler 环游问题。

那么现在我们来看另一个更难的问题: the Chinese Postman Problem (CPP)

(注:下文顶点和结点混用,但其实是一回事,vertex or vertice)

 

一些记号

环游就是从结点 v_0 出发最终回到 v_0 的一个有序路径。

在一个无向正权图上,经过每条边至少一次的环游的权是经过边的权值与次数的乘积的和。

即: v_0e_1,v_1e_2,\cdots ,e_nv_0 的权为 \sum_{i=1}^{n} w_{e_i}

图的最优环游就是该图的最小权的环游。

 

问题描述

那么这个问题是这样被描述的:

给定一个无向正权联通图,求出最优环游。

 

求解

第一,如果图是一个 Euler 图,那么显然任意一个 Euler 环游都是一个最优环游。

第二:非 Euler 图

把这个图记为 G

我们使用一种方法就是重复边法,说白了很简单,我们先假设答案已经求得,我们先规定每条边只能经过一次,然后把答案中重复的边拆成多条边,在原图上画出。

记这个新图为 G' ,这个 G' 显然是一个 Euler 图。

那么我们的任务就是构造出这样一个 Euler 图 G' 并且让它添加的边(称为重复边)的边权总和 W 最小。

 

Edmonds-Johnson 算法

case 1: G 正好有两个奇次(度)顶点

记这两个顶点为 S,T ,跑最短路即可。

case 2: G2n 个奇次顶点

我们使用 Edmonds 最小对集算法

思想:就是把 case 1 推广到了多组顶点上。

先用随便什么方法求出所有奇次顶点之间的最短路。 (Floyd or Dijkstra)

然后以这些奇次顶点为点集,做一个完全图,边权是两点间最短路。该图记为 G_1

我们跑带花树求出 G_1 的最小权完美匹配。(取负跑最大权完美匹配)

然后就做完了。

case 3:其余情况无解

 

注: 带花树写的只要不丑,差不多110行多点(含头文件IO等)。

注:我不会写。


2-SAT问题

缓更,但今晚肯定会更。

 

 

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是点数)