最近停课集训算是让我短时间内也接触了不少图论模型，再加上之前的，够我写一篇文了。
在这篇里面我并不想谈关于 弦图，区间图，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 的, 但在某些限制条件下它可以在多项式时间内解决.
Pollak−Gilbert 猜想
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 转移得到。
第一种转移：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
for (j = 0 to (1<<n)-1) { for (i = 1 to n) if (i in j) { for (sub=(j-1)&j;sub;sub=(sub-1)&j) { dp[i][j]=min(dp[i][j],dp[i][sub]+dp[i][j-sub]); } if dp[i] isnot INF { que.push(i); vis[i]=1; } } SPFA_Update(j); } |
除了枚举子集去更新之外，不要忘记要把有效状态放入队列。
第二种转移：
|
1 2 3 4 5 6 7 8 9 |
void SPFA_Update(int state) { //SPFA //如何更新呢 if (dp[v][state]>dp[u][state]+edge.cost) { dp[v][state]=dp[u][state]+edge.cost; } } |
复杂度分析
我们枚举子集的复杂度应是 n \times \sum (C_k^i \times 2^i) = n \times 3^k
那个 SPFA 的复杂度是 n \times 2^k 。
那么就是 O(n \times 3^k) 。
流程回顾
|
1 2 3 4 5 6 7 8 |
枚举状态集S { 枚举S的子集s { 更新dp[S][1~n],将 dp[S][x]<inf 的x入队 } SPFA更新(S) } |
Advanced: 斯坦纳森林问题
并没有多大难度。
考虑这样一件事情：我们给定并非一组 terminals ，我们给定 k 组。
对于这 k 组 terminals ，我们只要求同组中的是互相联通的。求一个生成树的最小花费方案。
那么我们可以这样：
我们枚举一个状态 w , 然后我们把 w 二进制拆分对应的几个集合中的 terminals 看成一组 terminals 。然后去做 STP。
然后我们求全集的答案就是再次子集DP一遍：
|
1 2 3 4 5 6 7 8 9 10 11 12 |
for (w = 0 to (1<<k)-1) { STP(w); } for (w = 0 to (1<<k)-1) { for (sub=(w-1)&w;sub;sub=(sub-1)&w) { DP[w]=min(DP[w],DP[sub]+DP[w-sub]); } } ans = DP[(1<<k)-1]; |
就很简单做完了。
图的遍历问题
这个问题比较有来头，他牵涉到了图论的起源（或者说创生？）
背景是著名的所谓 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: G 有 2n 个奇次顶点
我们使用 Edmonds 最小对集算法
思想：就是把 case 1 推广到了多组顶点上。
先用随便什么方法求出所有奇次顶点之间的最短路。 (Floyd or Dijkstra)
然后以这些奇次顶点为点集，做一个完全图，边权是两点间最短路。该图记为 G_1 。
我们跑带花树求出 G_1 的最小权完美匹配。(取负跑最大权完美匹配）
然后就做完了。
case 3:其余情况无解
注: 带花树写的只要不丑，差不多110行多点(含头文件IO等)。
注：我不会写。
2-SAT问题
缓更，但今晚肯定会更。