关于 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)

[SCOI2008] 天平

差分约束,套路地连边,套路地枚举得到答案

c1: \min(A-i) > \min(j-B)

c3: \min(i-A) > \min(B-j)

c2: \min(A-i)=\max(A-i) \,\, \min(B-j)=\max(B-j) \,\, A-i=B-j

具体式子看代码吧:

 

洛谷 P1660 数位平方和

最大的 xS(999999) \,\, (K=6) ,这个数字是 3188646 。其余待求函数值的 x 都小于这个数字。

所以最多是 4 \times 10^6 个元素求函数值然后再求个和,直接暴力。

试一下样例发现会出环,环上答案为环上最小值。

做完了。

 

HDU 1534 Schedule Problem

考虑把几个约束关系用数学式子描述( s 为起始时间,v 为持续时间)

FAF: s_a + v_a \geqslant s_b + v_b \rightarrow s_a - s_b \geqslant v_b - v_a

FAS: s_a + v_a \geqslant s_b \rightarrow s_a - s_b \geqslant - v_a

SAF: s_a \geqslant s_b + v_b \rightarrow s_a - s_b \geqslant v_b

SAS: s_a \geqslant s_b \rightarrow s_a - s_b \geqslant 0

然后暴力建图最长路

注意判正环。

这题可以说很入门了 😉

 

POJ 1364 King

继续套路地把每个位置 a_i 拿出来当做“值”。

然后再套路地把前缀和搞出来 s_i = \sum_{j=1}^i{a_j}

然后题面的约束条件就成了:

s_r - s_{l-1} > ki

s_r - s_{l-1} < ki

差分约束用的是 \leqslant\geqslant 。 

那么就全转化成 A - B \leqslant C 算了。

那么就

s_{l-1} - s_r \leqslant -1-k

s_{r} - s_{l-1} \leqslant k-1

判负环。

 

POJ 1201 Intervals

首先复习一下差分约束系统建图基本知识:

  • 对于约束条件 a-b \leqslant c ,我们建 b \rightarrow a 的边,权为 c
  • 这个时候求图的最短路,得到的是最大解。(负环无解
  • 对于约束条件 a-b \geqslant c ,我们建 b \rightarrow a 的边,权为 c
  • 这个时候求图的最长路,得到的是最小解。(正环无解

我们来观察这个题。

尝试向差分约束去靠拢,那么观察题面,条件是

r_i - l_{i-1} \geqslant c_i

这玩意怎么来的呢? 首先我们把这个题看成“选子集”的问题(一个位置代表一个元素)

套路地,我们设 x_i 是第 i 位置的”值” ( 选中-> 1 未选中-> 0 )

套路地,我们设 s_i 是前 i 位置”值”的前缀和。

那么就可以得出以上的约束式。

并且以这样的转化,我们一定可以建立关系

0 \leqslant s_{i} - s_{i-1} \leqslant 1

这些关系已经够了。但是有个地方很不舒服,就是上面的两个 \leqslant

把式子倒过来:

s_{i} - s_{i-1} \geqslant 0

s_{i-1} - s_{i} \geqslant -1  

做完了。

注意 s_{0-1} 会爆炸所以把所有下标 +1

 

从特殊的图论模型谈开去

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

在这篇里面我并不想谈关于 弦图,区间图,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问题

缓更,但今晚肯定会更。

 

 

弦图,区间图,完美消除,MCS,TreeDecp,PQTree及其他

BKG:某天晚上和dkw闲聊,然后随机到了一个题(ZOJ1015 Fishing Net)。

想了半天不会做。不久之后dkw说他看了题解……然后我们就找来了这个课件。。


感觉还是挺魔性的。

今天T3也是一个Chord Graph TAT.

行,现在开始抄课件.

 

图的定义

子图

G=(V,E), G'=(V',E'),V' \subseteq V , E' \subseteq E 为图 G 的子图。

诱导子图

G'=(V',E'),V' \subseteq V,E'=\{(u,v)|u,v \in V',(u,v) \in E \} 称为 G 的诱导子图。

G 的一个子图 G',满足 G' 为关于 V' 的完全图。

极大团

一个团是极大团,当它不是其他团的子集。

最大团

点数最多的团。记为 \omega (G) 

最小染色

用最少的颜色给点染色使相邻点颜色不同。色数记为 \chi (G) .

最大独立集

一个点集的最大子集使得任意两个点不连通。记为 \alpha (G) .

最小团覆盖

可以覆盖所有的点的最小团数。团数记为 \kappa (G) .

定理

\omega (G) \leqslant \chi (G) .

\alpha (G) \leqslant \kappa (G) .

弦(Chord)

连接环中的不相邻两个点的边。

弦图

一个无向图,图中任意长度 \geqslant 3 的环都至少有一个弦。

 

定理

弦图的每一个诱导子图一定是弦图。

弦图的任一个诱导子图不同构于 C_n \; (n>3)(?)

弦图判定

单纯点

一个点称为单纯点,当它和与它相连的所有点构成的诱导子图是一个团。

Lemma

任何一个弦图有至少一个单纯点,不是完全图的弦图至少有两个不相邻的单纯点。

完美消除序列

一个点组成的序列 v_1,v_2,v_3,\cdots ,v_n ,满足 v_i \{ v_i,v_{i+1},\cdots,v_n \} 的诱导子图中是一个单纯点。

定理

一个无向图是一个弦图,当且仅当它有一个完美消除序列。

证明:略,详见课件qwq

Lexicographic BFS (LexBFS,字典序BFS)

实现困难又难记,我选择不写。

时间复杂度O(n+m) .

MCS (Maximum Cardinality Search,最大势算法)

这个算法要做的就是按照从 n1 顺序依次给每个点标号。标号为 i 的点是完美消除序列中的第 i 个点。

l[i] 表示第 i 个点与多少个已经标号的点相邻,每次选择一个 l 最大的未标号点进行标号。

😕 这个代码挺好的,但是有一点问题就是如何维护largest label.

有一个做法就是维护一个链表,并维护最大值。这样每次更新 \mathrm{label} 都是 O(1) 左右的。

还要啰嗦一句的是,存在MCS和BFS都得不到的完美消除序列。(但是我不会找……  🙁 )

相邻点判定完美消除序列(判定弦图)

1 \sim n 枚举序列中的每个点。

\{ v_{i+1},\cdots ,v_n \} 中所有与 v_i 相邻的点依次为 v_{j1},\cdots,v_{jk}

每次判断 v_{j1} 是否与 v_{j2},\cdots,v_{jk} 相邻即可。

时间复杂度 O(n+m)算法的正确性证明咕了,等我翻完论文看看有没有给出。

CODE

这份是 BZOJ1242 的代码,这玩意包括了求一个图的 PEO (Perfect Elimination Orderings) 和判定一张图是不是弦图 QAQ

(这段文字和这篇文章的首发差了半年的时间,233

弦图相关

寻找极大团

Lemma

设第 i 个点在弦图的完美消除序列的第 p(i) 个。

N(v)= \{ w | w \text{与} v \text{相邻且} p(w)>p(v) \} ,那么弦图的极大团一定是 v \cup N(v) 的形式。

推论

弦图最多有 n 个极大团。

我们只需要判定每个 v \cup N(v) 是否为极大团。

A = v \cup N(v) , 若存在 B = w \cup N(w) 使得 A \subseteq BA 不是极大团。

首先我们可以得到 p(w)<p(v)

\mathrm{next} (v) 表示 N(v) 中最前的点, w* 表示在所有满足 A \subseteq Bw 中最后的一个点。

可知 \mathrm{next} (w*) = v 。若不是,则 \mathrm{next} (w*) 也是一个满足上述条件的点,得证。

那么, v \cup N(v) \subseteq w \cup N(w) 当且仅当 | N(v) | +1 \leqslant | N(w) |

我们只需要判定是否存在一个 w ,满足 \mathrm{next} (w) = v| N(v) | +1 \leqslant | N(w) | 即可。

时间复杂度 O(n+m)

 

<<此处本应有代码>>

 

弦图点染色

行……我们终于来到了这个题……

HNOI2008 神奇的国度。

用最少的颜色给每个点染色,使得相邻的点染色不同。

有一个神奇的做法:

求出完美消除序列,从后向前给每个点染上可以染的最小色。

团数=色数。证明:比较简单,咕了,看课件吧

O(n+m)

弦图最大独立集,最小团覆盖

最大独立集:完美消除序列从前往后能选就选。

最小团覆盖:最大独立集的每个点都与它的邻点组成一个团,以此求出最小团覆盖。

\alpha (G) = \kappa (G)

区间图

定义

在序列上给定一些区间,定义一个相交图为:

  1. 每个顶点表示一个区间
  2. 两点之间有边,当且仅当对应代表的区间的交集非空。

如果一个图是若干区间的相交图,则它是区间图。

定理

区间图一定是弦图。

证明略,详见课件。

区间图完美消除序列

将所有的区间按照右端点从小到大排序。

没了。。。证明depends on我能不能找到了

区间图最大独立集

问题:给定 n 个区间,求一个选择最多区间的方案,使得所有区间的交集为空。

Sol:最裸的题,最大独立集。完美消除序列上的判定可以做到 O(n\log _2 n)   (线段树或堆),非常优秀。

区间图最小染色

n 个高度均为 1 的积木,第 i 个位于 [L_i,R_i] 的位置   (也就是起点在 L_i ,宽 R_i-L_i )。

求一个积木下落顺序,使得最后积木总高度尽可能小。

就是求一个最小染色,方案则是按照颜色编号从小到大掉落。

一个很意识流的解释就是尽量让不交的区间落在一层上。

更多实现上的细节:我们可以倒过来排序,然后依次处理。也是 O(n \log _2 n) 的。

判定区间图

  • 判定是否为弦图。
  • 找出所有的极大团。
  • 构建一个 顶点-团矩阵 A ,使得 A 的每一行代表 G 的一个顶点,每一列代表 G 的极大团。满足 A_{ij}=\begin{cases} 1 \; \mathrm{if} \; v_i \in C_j \\ 0 \; \mathrm{otherwise} \end{cases}
  • 判断是否存在一个重排方式,即任意交换 A 的各列,使得每行的所有 1 都是连续的。如果这种排列存在,就称这个矩阵具有连续 1 性质。
  • 可以用PQTree来实现(这就是作死)

 

  • 另外一种判定方法
  • 《A new Test for Interval Graphs》


 

Tree Decomposition

一个无向图 G=(V,E) 的 树的分解(Tree Decomposition) 定义为 (X,T) ,\; X= \{ X_1,X_2, \cdots ,X_m \} ,其中 X_iV 的一个子集, T 是一棵树,点集为 X

一些性质

X_1 \cup X_2 \cup \cdots \cup X_m = V

对于 G 中任意一条边 (u,v) \;,\; \exists X_i 使得 u,v \in X_i

对于每个点 v,P(v)= \{ X_i | v \in X_i \} ,则 TP(v) 的诱导子图是联通的。

所以这玩意到底有啥用啊 🙁

Clique Tree

clique tree是一种tree decomposition.

一个无向图 G 为弦图当且仅当存在一个clique tree.

一个无向图为区间图当且仅当存在一个链形态的clique tree

所以这玩意到底又有啥用啊 🙁

构建弦图Clique Tree

感觉这玩意没用。我Bing了一下Clique Tree看到的全是概率学玄学……

愿意学的看课件吧。

 

 

 

 

 

 

 

 

 

 

 

BZOJ1016 | JSOI2008 最小生成树计数

题面不放

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

其实暴搜可过

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

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

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

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

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

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

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

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

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

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

 

点击图片跳转原题

 

 

 

 

 

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