MST.tex

\section{最小生成树}
\subsection{Kruskal与LCT}
Luogu P4234 最小差值生成树\footnote{【P4234】最小差值生成树 - 洛谷
	\url{https://www.luogu.org/problemnew/show/P4234}
}

按照Kruskal的处理顺序处理生成树，当遇到环时删掉环上权值最小的边，然后连上自己。

\subsection{动态MST}
支持插入边，删除边，修改边权，每次修改后回答MST的代价，可离线。

首先处理涉及到的所有边，边不存在时记其边权为$\infty$，那么插入边和删除边都可以
转化为修改边权解决。对应的题目为[HNOI2010]城市建设。

若边权是不增的，很容易使用LCT维护树形结构，对于非树边，每次查询两端在MST上的链上
最大权边，讨论是否将其换下。

对于边权可增的情况，若增权的边在MST上，则需要查询跨连通块的最小非树边，并讨论是否替换。
这个询问不好做。注意到修改可离线，考虑使用分治解决。

在这$k$个修改操作中，产生了$k$个MST，有些边一定不出现在MST中，有些边一定出现在MST中。
一定不出现的边可以直接删除，一定出现的边可以使用并查集连起来，分别减少了边数和点数，缩减
图的规模。

处理无用边：将有修改的边标记为$\infty$，做MST，删去无修改且不在MST中的边。

处理必须边：将有修改的边标记为$-\infty$，做MST，连接无修改且在MST中的边。

每次处理$[l,r]$区间内的修改，然后递归到左右部分处理，每次递归时都能缩减图的规模。
当缩减到只有一个修改时暴力对剩下的边做MST。递归右边前要执行左边的修改。

参考代码：
\lstinputlisting{Source/Source/CDQ/3206.cpp}

上述内容参考了顾昱洲的课件《浅谈一类分治算法》。
\subsection{Prim算法}

从一个点开始贪心地连接最短的可扩展边，直至每个点都被连接。

代码：
\begin{lstlisting}
struct Info{
    int u,d;
    Info(int u,int d):u(u),d(d){}
    bool operator<(const Info& rhs) const {
        return d>rhs.d;
    }
};
bool flag[size];
int prim(int n) {
    flag[1]=true;
    std::priority_queue<Info> heap;
    for(int i=last[1];i;i=E[i].nxt)
        heap.push(Info(E[i].to,E[i].w));
    int cnt=1,sum=0;
    while(cnt<n && heap.size()) {
        int u=heap.top().u;
        int d=heap.top().d;
        heap.pop();
        if(!flag[u]) {
            flag[u]=true;
            sum+=E[i].w;
            for(int i=last[u];i;i=E[i].nxt) {
                int v=E[i].to;
                if(!flag[v])
                    heap.push(Info(v,E[i].w));
            }
        }
    }
    return cnt==n?sum:-1;
}
\end{lstlisting}

当边数较大时，可以考虑使用Prim或优先队列+Kruskal（参见第~\ref{PQS}\\节）。

\subsection{次小生成树}
步骤如下：
\begin{enumerate}
	\item 构造最小生成树，标记并连接树边；
	\item 对生成树进行树链剖分，构造线段树，使其可以$O(\lg n)$查询到链上最大权；
	\item 枚举非树边，计算其替代链上的最大边后的代价，更新答案。
\end{enumerate}

对于严格次小生成树，需要维护链上最大权与严格次大权。

\subsection{生成树性质}
以下性质用于解决最小生成树计数问题：
\begin{property}
	最小生成树中,不同权值边的数量固定。
\end{property}
\begin{property}
	Kruskal算法中,处理完某一权值的边后，连通块相同。
\end{property}
\subsubsection{例题}

Luogu P4208 [JSOI2008]最小生成树计数\footnote{
【P4208】[JSOI2008]最小生成树计数 - 洛谷
\url{https://www.luogu.org/problemnew/show/P4208}
}

根据以上两个性质可以把每种权值的边分别计算，然后使用乘法原理组合即为答案。

步骤如下：
\begin{enumerate}
	\item 首先使用常规Kruskal计算每种权值边的数量$c_i$以及等权边的分布区间；
	\item 对于每一种权值，计算用完$c_i$条边的方案数。
	      由于题中每种权值的边数不超过10，可以枚举每条边选还是不选，
          在回溯时直接令连接的两点的根的父亲重设为自己，时间复杂度近似为$O(2^{c_i})$。
          模拟对该权值边做Kruskal的过程。
	\item 把每种权值的方案数乘起来就是方案数。
\end{enumerate}

代码如下：
\lstinputlisting{Source/Unclassified/Done/4208.cpp}

另一种方法：每次计算小连通块->大连通块的过程，对于每个大连通块单独使用
Matrix-Tree定理求方案数，方案数之积即为答案。

最小生成树计数问题参考了clover\_hxy的博客\footnote{
bzoj 1016: [JSOI2008]最小生成树计数 （矩阵树定理+最小生成树）
\url{https://blog.csdn.net/clover\_hxy/article/details/69397184}
}。
\subsection{Boruvka算法}
\index{B!Borůvka's Algorithm}
当边数较大时，还可以使用Boruvka算法，该算法像多路的Kruskal算法。

算法步骤如下：
\begin{enumerate}
    \item 把每个点初始化为一个连通块。
    \item 对每个连通块查询其连出的最小权值边。
    \item 加入所有边，若边权两两不同则不可能出现环。一般用并查集判环。
    \item 重复步骤2直至生成树构造完毕。
\end{enumerate}

由于每次迭代后连通块数至少减少一半，共需合并$O(\lg n)$次。每次合并后
由于连通块的变化而重建数据结构的复杂度是可以接受的。插入时需要把连通块
编号存入，维护连通块编号的最值，以便于查询时排除块内边。

模板（CF888G Xor-MST）：
\lstinputlisting{Source/Templates/Boruvka.cpp}
\subsection{单点度限制最小生成树}
要求指定点$v_0$的度数为$k$，求MST。

首先把原图去掉$v_0$求最小生成森林，此时这些连通块只能通过$v_0$与之相连。
若连通块数$>k$，则无解。然后每个连通块内选择一条边权最小的边连向$v_0$。若
连通块数$<k$则不断选择块外未选择边连上$v_0$，然后切断对应连通块。

该内容参考了唐文斌在WC2012上的讲稿《图论专题之生成树》。
\index{*TODO!单点度限制最小生成树实现}