有一类树上背包（例如 CF1097G Vladislav and a Great Legend），第二维表示子树内选的点数且限制第二维不超过$m$，其总复杂度可证明为$O(nm)$。

它们的代码一般长这样：

1
2
3
4
5
6
7
8
9
10
11
12

void dfs(int u,int last) {
	sz[u]=1;
	// initialize dp[u]
	for(int k=head[u];k;k=e[k].next)
	{
		int v=e[k].to; if(v==last) continue;
		dfs(v,u);
		for(int j=0;j<=min(m,sz[u]);++j)
			for(int k=0;k<=min(m-j,sz[v]);++k)
				// dp[u][j] * dp[v][k] -> dp[u][j+k]
	}
}

问题

求一个任意的无向图的全局最小割。即，定义$\lambda(x,y)$表示$x,y$两点之间的最小割，给出一张任意的无向图，你需要求出$\min_{x\neq y}\lambda(x,y)$。

Stoer-Wagner 算法

基本定义

割 cut

对于一张带权无向图$G=(V,E)$，定义一个割 (cut)为两个集合$S,T\in V$，满足$S\cap T = \emptyset, S\cup T = V$。定义一条边为割边 (cut edge)当且仅当它的两个端点分别在$S$集合和$T$集合内。定义一个割的容量 (capacity of a cut)为所有的割边的边权的和。

一般图

复杂度主要取决于dfs增广的过程。

将dfs部分的复杂度分成两部分来分析：1）修改增广路上边的流量。至多会增广$m$次，一条增广路的长度至多是$n$，所以这一部分的复杂度是$O(nm)$。2）dfs遍历时找增广路失败时经过的边。由于一旦从某条边出发找最短路失败了，我们就不会再走那条边（当前弧优化），所以这一部分的复杂度是$O(m)$的。故而dfs增广的复杂度是$O(nm)$。

问题

有$n$个男生和$n$个女生，有$2n$个排列$p_1,p_2\cdots p_n,q_1,q_2\cdots q_n$，$p_i$代表第$i$个男生的喜好（$p_{i,1}$表示他最喜欢的女生，$p_{i,2}$是他第二喜欢的，以此类推），$q_i$代表第$i$个女生的喜好。

稳定婚姻问题即，求一个男生和女生的完美匹配$M$，使得不存在$(x,y)\not\in M$，$x$对$y$的好感高于$x$现在的配偶且$y$对$x$的好感高于$y$现在的配偶。

定义

有一张无向图$(V,E)$，指定了一个$V$的子集$S$，需要求出一个边集$E’$，使得：

• 对于任意两个点$x,y\in S$，存在一条从$x$到$y$的、由$E’$中的边组成的路径（路径可以经过不在$S$中的点）。
• 在此基础上，最小化$E’$中所有的边的边权和。

Hall’s marriage theorem

定理内容

这个定理是说，对于任意一个二分图$G=\{ X+Y,E\}$，都有：
$\forall W \subset X, |W|\le |N_G(W)| \Longleftrightarrow |M|=|X|$
其中，$N_G(W)$表示$Y$中与$W$中的点相邻的点的集合，$M$表示最大匹配。

三元环计数

解决方法

1.将无向边改成有向边，令度数大的点指向度数小的点；如果度数相同，就让编号大的点指向编号小的点。（这一步也可以是，度数小的点指向度数大的点；度数相同比较编号）
2.枚举一个点u。
3.标记所有u的出边可以到达的点。
4.枚举一个u的出边可以到达的点v，然后再枚举一个v的出边可以到达的点w，如果w被标记过，说明u,v,w构成三元环，ans++

两条路径$u_1\to v_1,u_2\to v_2$的交这样计算：

• 首先计算出$x_1=lca(u_1,u_2),x_2=lca(v_1,v_2),x_3=lca(u_1,v_2),x_4=lca(v_1,u_2)$，然后取这四个点中深度最大的两个点$y_1,y_2$。
• 若$y_1=y_2$，且$y_1$的深度大于了$lca(u_1,v_1)$或者$lca(u_2,v_2)$的深度，那么交不存在；否则，交就是$y_1$到$y_2$之间的路径。

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

// Road中的t：t=0表示空集，t=-1表示全集，t=1表示u到v的路径
struct Road {
	int u,v,t;
	Road(int u=0,int v=0,int t=-1): u(u),v(v),t(t){};
};
bool cmp_dep(int x,int y) { return dep[x]>dep[y]; }
Road Inter(Road A,Road B) {
	if(A.t==0||B.t==0) return Road(0,0,0);
	if(A.t==-1) return B;
	if(B.t==-1) return A;
	int tmp[4]={LCA(A.v,B.v),LCA(A.u,B.u),LCA(A.v,B.u),LCA(A.u,B.v)};
	sort(tmp,tmp+4,cmp_dep);
	if(tmp[0]==tmp[1]&&(dep[tmp[0]]<dep[LCA(A.u,A.v)]||dep[tmp[0]]<dep[LCA(B.u,B.v)]))
		return Road(0,0,0);
	return Road(tmp[0],tmp[1],1);
}
bool Onchain(Road A,int x) {
	if(A.t==0) return 0;
	if(A.t==-1) return 1;
	if(A.t==-1) return 1;
	int tmp[2]={LCA(A.u,x),LCA(A.v,x)};
	if(dep[tmp[0]]<dep[tmp[1]]) swap(tmp[0],tmp[1]);
	if(tmp[0]==x&&tmp[1]==LCA(A.u,A.v)) return 1;
	return 0;
}

这个算法用于求解有向图的最小树形图问题。

树形图：图中有一个点作为根，除了根以外，每个点的入度恰好为$1$，并且从根出发可以到达整个图中的任意一个点。

最小树形图就是所有边的边权和最小的树形图。