各种小知识点

Kruskal 重构树

Steiner 树

两道例题：

BZOJ3205 APIO2013 机器人
BZOJ2595 WC2008 游览计划

求 \(N\) 个点的连通无向图中至少包含给定的 \(K\) 个点的最小生成树。

\(S\) 表示连通状态， \(p\) 是当前状态中用来考虑转移的节点，可以理解成暂时的根之类的东西。

\[f(S,p)=min\{f(A,p)+f(B,p)\ |\ A\ or\ B = S\}\\f(S,p)=min\{f(S,q)+val(p)\}\]

第一个转移直接 DP ，第二个转移要求 \(p\) 和 \(q\) 关联，用图论算法转移。它的正确性好像来自什么三角形不等式，不懂，不过确实可以感性理解。

注意 SPFA 可以加个 Small Label First 优化，开两个队列，每次取最小的来扩展，特殊情况下就是个 BFS 。

给自己留一份伪代码：

void spfa(int s)
{
    sort(Que_A);
    ...
    while () {
        p = min(Que_A.head, Que_B.head);
        ...
        for (...) {
            if (F[s][y] > F[s][x] + w) {
                ...
                Que_B.push(...);
            }
        }
    }
    return;
}

void steiner()
{
    for (int s = 0; s != (1 << K); ++s) {
        for (int t = (s - 1) & 1; t; t = (t - 1) & 1) {
            for (int p = 1; p <= N; ++p)
                F[s][p] = min(F[s][p], F[t][p] + F[s ^ t][p]);
        }
        for (int p = 1; p <= N; ++p)
            if (F[s][p] < INF)
                Que_A[++Q_cnt] = data(p, F[s][p]);
        spfa(s);
    }
    int ans = INF;
    for (int i = 1; i <= N; ++i)
        ans = min(ans, F[(1 << K) - 1][i]);
    return;
}

虚树

树很大，需要考虑的点很少，弄一颗虚树。树上路径求交的方法是把点集按 dfn 排序，然后相邻两个点找 lca 记录路径，这些路径是无公共边的。虚数也是先排序，然后用栈维护 dfn 递增的一条从根到当前讨论的点的链，最后在栈底的就是虚数的根。

void ins_node(int p)
{
    if (Top <= 1) {
        S[++Top] = p;
        return;
    }
    int lca = get_lca(p, S[Top]);
    if (lca == S[top]) {
        S[++Top] = p;
        return;
    }
    while (Top > 1 && Dfn[lca] <= Dfn[S[Top - 1]])
        ins_edge(S[Top - 1], S[Top]), --Top;
    if (lca != S[Top])
        ins_edge(lca, S[Top]), S[top] = lca;
    S[++Top] = p;
    return;
}

图论-怅望祁连

原文：https://www.cnblogs.com/ghcred/p/10284942.html