【图论】最短路、树、图、二分匹配
有根树计数
设
$$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和一棵树一一对应
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标号实现同时查找多条最短增广路。
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)$
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
见斯坦纳树