有根树计数

设

$$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标号实现同时查找多条最短增广路。

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

见斯坦纳树