【图论】最短路、树、图、二分匹配

NanoApe posted @ 2016年1月08日 20:35 in 蒟蒻不撕烤智熵何来 , 1399 阅读

有根树计数

设

$S_{n,j}=\sum_{i=1}^{n/j}a_{n+1-ij}=S_{n-j,j}+a_{n+1-j}$

n+1个结点的有根树的总数为：

$a_{n+1}=\frac {\sum_{j=1}^n j a_j S_{n,j}}{n}$

无根树计数

当 $n$ 是奇数时

$Cnt=a_n-\sum_{i=1}^{n/2}a_i a_{n-i}$

当 $n$ 是偶数时

$Cnt=a_n-\sum_{i=1}^{n/2}a_i a_{n-i}+\frac{1}{2}a_{n/2}(a_{n/2}+1)$

Prufer Sequence

由树得到序列：

总共需要 $n-2$ 步，第 $i$ 步在当前的树中寻找具有最小标号的叶子节点，将与其相连的点的标号设为PruferSequence的第 $i$ 个元素 $P_i$ ，并将此叶子节点从树中删除，直到最后得到一个长度为 $n-2$ 的PruferSequence和一个只有两个节点的树

由序列得到树：

先将所有点的度赋初值为1，然后加上它的编号在PruferSequence中出现的次数，得到每个点的度

执行 $n-2$ 步，第 $i$ 步选取具有最小标号的度为1的点 $u$ 与 $v=P_i$ 相连，得到树中的一条边，并将u和v的度减一

最后再把剩下的两个度为1的点连边，加入到树中

性质：

一个PruferSequence和一棵树一一对应

（一篇对于PruferSequence解释得不错的文章）

Matrix-Tree定理&Kirchhoff矩阵

定义图G的Kirchhoff矩阵C=度数矩阵D-邻接矩阵A

此图的生成树个数即为C的任一N-1阶主子式的绝对值

SPFA优化

SLF优化：若当期要加入到队列的点的 Dist 小于队首的 Dist，则将点加入到队首

LLL优化：若队首的 Dist 大于队列中的平均 Dist，则将队首移到队末

差分约束

若要使得所有量两两的值最接近，则将如果将源点到各点的距离初始化为0

若要使得某一变量与其余变量的差最大，则将源点到各点的距离初始化为 $\infty$ ，某一变量所代表的点为0

若求最小方案则跑最长路，否则跑最短路

平面图-欧拉定理

$F-E+V=2$

其中F为面数，E为边数，V为顶点数

二分图性质

最小路径覆盖=总点数-最大匹配数（DAG图+拆点）

最小覆盖点集=最大匹配数（DAG图）

最大权值环覆盖=最大完美匹配

最小改动最大匹配：所有边的权值乘上n，然后对于原匹配的边则加一，改图后求最大完美匹配

弦图-MCS最大势算法

选取未标号中标记最多的点i，将点i加到完美消除序列，然后增加与点i相连的未标号点的标记

扩展：

求最小染色数：求出完美消除序列后，从后往前染上最小能染的颜色

求最大独立集：求出完美消除序列后，从前往后选择点，能选就选

Hopcroft-Karp算法

先通过DFS预处理出Dist标号，然后利用Dist标号实现同时查找多条最短增广路。

Hopcroft-Karp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15	`while` `(true)` `{` `queue<int>q; D=inf;` `rep(i, 1, n)` `if` `(!choose[i]) q.push(i), d[i]=0;` `else` `d[i]=inf;` `while` `(!q.empty())` `{` `int` `x=q.front(); q.pop();` `if` `(d[x]>=D)` `break;` `travel(x)` `if` `(!k[p->y]) D=d[x];` `else` `if` `(d[k[p->y]]==inf) d[k[p->y]]=d[x]+2, q.push(k[p->y]);` `}` `Cnt++; rep(i, 1, n)` `if` `(!choose[i] && Find(i)) A3++, choose[i]=1;` `//套上匈牙利` `//答案更新则continue` `}`

二分图最大权匹配

复杂度为 $O(n^3)$ ，写残会退化成 $O(n^4)$

KM
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41	`bool` `Find(int` `x,` `int` `y)` `{` `rep(o, 1, n)` `if` `(!v[o])` `{` `if` `(lx[x]+ly[o]<=c[x][o])` `{` `h[o]=y; v[o]=true;` `if` `(!k[o] \|\| Find(k[o], o))` `return` `k[o]=x,` `true;` `}` `else` `if` `(st[o]>lx[x]+ly[o]-c[x][o])` `st[o]=lx[x]+ly[o]-c[x][o], h[o]=y;` `}` `return` `false;` `}` `int` `main()` `{` `nx=read(), ny=read(); n=max(nx,ny);` `m=read();` `while` `(m--)` `{` `int` `x=read(), y=read();` `c[x][y]=max(c[x][y],read()); lx[x]=max(lx[x],c[x][y]);` `}` `rep(x, 1, n)` `{` `rep(y, 1, n) st[y]=inf, v[y]=false, h[y]=0;` `int` `X=x, Y=0;` `while` `(!Find(X,Y))` `{` `int` `a=inf; rep(y, 1, n)` `if` `(!v[y]) a=min(a,st[y]);` `if` `(a==inf)` `break;` `lx[x]-=a; rep(y, 1, n)` `if` `(!v[y]) st[y]-=a;` `else` `ly[y]+=a, lx[k[y]]-=a;` `rep(y, 1, n)` `if` `(!v[y] && !st[y]) {Y=y;` `break;}` `if` `(k[Y]) v[Y]=1, X=k[Y];` `else` `break;` `}` `if` `(Y)` `{` `while` `(h[Y]) k[Y]=k[h[Y]], Y=h[Y]; k[Y]=x;` `}` `}` `return` `0;` `}`

包含给定点的MST

见斯坦纳树

NanoApe's Blog

既是咸鱼又是辣鸡