NanoApe's Blog

既是咸鱼又是辣鸡

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

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

 

有根树计数

$$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

斯坦纳树

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter