洛谷 P4716 Lutece 2733 POJ3164 最小树形图模板

19 April 2022 | duanyll | Tags: OI 题解图论

题意

最小树形图是有向图上，从给定的根节点出发到达所有节点的一颗生成树。

分析

求解最小树形图的一种算法是$O(mn)$的朱刘算法。

考虑给除根节点外的每个点寻找一条最小的入边，如果找出的入边恰好构成一棵树，则容易证明这样的情况¹是最优解。如果找不出入边，说明最小树形图不存在。

对于找出的入边构成环的情况，朱刘算法提出可以通过不断地将环缩成点来处理。枚举最小入边的过程保证每个环上只需要断开一条边，而且断开处的节点可能需要寻找一条环外的入边。所以可以先将环上所有边的边权都统计到答案中，然后对于环上每个点，将环外的入边都减去环上入边的边权，这样缩环为点以后，再选择到被处理过边权的入边时，就相当于确定了断开环的位置。之后，再重复枚举最小入边和缩环的过程，直到没有环为止。

使用邻接矩阵存图时，缩环的具体操作，先选定环上的任意一个点，然后将环外连接其他点的边连接到该点上，重复的边权直接取最小，出边类似处理。之后，用一个数组给环上的其他点打上标记，之后的过程中不再枚举即可。

朱刘算法可清晰地划分为如下流程：

枚举所有点的入边
判断入边是否存在环
1. 不存在环，算法结束，返回答案
2. 找到一个环（有且仅有一个）
  1. 统计环上边权之和
  2. 所有环外入边的边权，减去环上入边的边权
  3. 将环上其余点的边转移到代表点上
  4. 给其余点打上删除标记
  5. 重复步骤 1

代码

洛谷的数据似乎强度很低，找环过程有明显错误的代码都能通过。

下面给出 Lutece 2733 的代码，与洛谷代码仅有数据范围的区别。

int g[MAXN][MAXN];
bool remove_tag[MAXN];  // 缩环时删点标记
int fa[MAXN];           // 每轮，每个点的最小前驱节点
bool vis[MAXN];         // 找环的标记

int directional_spawning_tree(int root, int n) {
    int ans = 0;
    memset(remove_tag, false, sizeof remove_tag);
    while (true) {
        // 找每个点的最小前驱边
        for (int u = 1; u <= n; u++) {
            if (remove_tag[u] || u == root) continue;
            int min_val = INF;
            int min_node = 0;
            for (int i = 1; i <= n; i++) {
                if (remove_tag[i]) continue;
                if (g[i][u] < min_val) {
                    min_val = g[i][u];
                    min_node = i;
                }
            }
            // 如果没有前驱，则无解
            if (min_node == 0) return -1;
            fa[u] = min_node;
        }

        // 判断是否有环
        bool has_loop = false;
        int loop_head = 0;
        for (int i = 1; i <= n; i++) {
            if (remove_tag[i] || i == root) continue;
            memset(vis, false, sizeof vis);
            vis[root] = true;
            int u = i;
            while (!vis[u]) {
                vis[u] = true;
                u = fa[u];
            }
            if (u != root) {
                has_loop = true;
                loop_head = u;
                break;
            }
        }

        if (!has_loop) {
            // 没有环，则算法结束
            for (int i = 1; i <= n; i++) {
                if (remove_tag[i] || i == root) continue;
                ans += g[fa[i]][i];
            }
            return ans;
        }

        // cout << loop_head << endl;

        // 进行缩环操作
        // 统计环上的权值
        int u = loop_head;
        do {
            ans += g[fa[u]][u];
            u = fa[u];
        } while (u != loop_head);

        // 然后处理环上所有入边的权值，入边权值减去环上边的权值
        // 这样缩环后再判断找最小前驱边时，选到入环的边就决定了断环的位置
        u = loop_head;
        do {
            for (int i = 1; i <= n; i++) {
                if (remove_tag[i]) continue;
                if (i != fa[u] && g[i][u] != INF) {
                    g[i][u] -= g[fa[u]][u];
                }
            }
            u = fa[u];
        } while (u != loop_head);

        // 缩点，转移权值
        for (int i = 1; i <= n; i++) {
            if (remove_tag[i] || i == loop_head) continue;
            int u = fa[loop_head];
            do {
                g[loop_head][i] = min(g[loop_head][i], g[u][i]);
                g[i][loop_head] = min(g[i][loop_head], g[i][u]);
                u = fa[u];
            } while (u != loop_head);
        }

        // 把环上其他的点都标记删除
        u = fa[loop_head];
        do {
            remove_tag[u] = true;
            u = fa[u];
        } while (u != loop_head);
    }
}

int main() {
    int n = read();
    int m = read();
    int r = read();
    memset(g, INF, sizeof g);
    for (int i = 1; i <= m; i++) {
        int u = read();
        int v = read();
        int w = read();
        g[u][v] = min(g[u][v], w);
    }
    int res = directional_spawning_tree(r, n);
    write(res);
}

其实随机生成的图几乎都符合这样的条件。 ↩