解题思路

本题要求我们在一个给定的图中，找到在不同连通块数量下，最多可以删除红色边获得的权值总和。这涉及到图的连通性和最小生成树（MST）的问题。我们将通过最小生成树（MST）来最优化删除红色边的策略，以最大化我们能够获得的权值。

最小生成树的基本概念

最小生成树是一个图的子图，它包括图中所有的节点，并且使得所有的边的总权值最小。

问题转化为最小生成树

在本题中，红色边的删除会增加连通块的数量，采用逆向思维，我们可以将问题转化为通过添加红色边，使得图的连通块数逐渐减小，且添加红色边后尽可能保留剩下红色边更大的权值。

思路分析

我们可以利用 Kruskal 算法来实现最小生成树的构建，并在过程中逐步考虑删除红色边。具体步骤如下：

1. 初始化并查集：

   • 我们使用并查集（Union-Find）来动态维护图中的连通块数。每次合并两个节点时，图中的连通块数减少。
   • 初始时，图的连通块数为 $n$（每个节点自己是一个连通块）。

2. 按权值排序红色边：

   • 将所有红色边按照权值从小到大排序。通过从小到大考虑这些边，我们尽量保留较小的红色边以减少连通块数量，且保留更多的权值。

3. 逐步添加权值小的红色边：

   • 对于每个 $k$，我们希望尽可能地减少连通块的数量到 $k$，并获得最大的权值。
   • 通过逐步合并节点，每合并一次，就意味着连通块数减少。
   • 未使用的红色边就是被删除的红色边。

4. 输出结果：

   • 最终，对于每个 $k$（从 $1$ 到 $n$），我们输出删除红色边后，连通块数不超过 $k$ 时能获得的最大权值总和。

算法步骤

1. 初始化：读入图的节点数 $n$ 和边数 $m$，并初始化并查集。
2. 处理红色边：将红色边按权值排序，准备按顺序进行处理。
3. 逐步合并：通过合并操作减少连通块数，并更新收益。
4. 输出结果：根据每个可能的连通块数量，输出对应的最大权值总和。

复杂度分析

• 时间复杂度：

  • 初始化并查集需要 $O(n)$。
  • 对所有边的处理（包括红色边的排序）需要 $O(m \log m)$，其中 $m$ 是边的数量。
  • 并查集的每次 find 和 union 操作的时间复杂度是 $O(\alpha(n))$，其中 $\alpha(n)$ 是阿克曼函数的反函数，接近常数时间。

  因此，总时间复杂度为 $O(m \log m + m \alpha(n))$，其中 $\alpha(n)$ 可以认为是常数，因此时间复杂度大致为 $O(m \log m)$。

• 空间复杂度：

  • 需要存储并查集的父节点、秩数组，空间复杂度为 $O(n)$。
  • 额外存储红色边的数组，空间复杂度为 $O(m)$。

Python 代码

import sys

# 并查集数据结构
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size + 1))  # parent[i]表示节点i的父节点
        self.rank = [0] * (size + 1)          # rank[i]表示节点i的秩（树的高度）
        self.count = size                     # 初始连通块数为n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]

    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return False  # x和y已经在同一个连通块，不需要合并
        if self.rank[x_root] < self.rank[y_root]:
            self.parent[x_root] = y_root
        else:
            self.parent[y_root] = x_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1
        self.count -= 1  # 合并后连通块数减1
        return True

def main():
    # 读入数据
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])  # 节点数
    ptr += 1
    m = int(input[ptr])  # 边数
    ptr += 1

    uf = UnionFind(n)  # 初始化并查集
    sum_red = 0  # 红色边的权值和
    red_edges = []  # 存储红色边

    # 读入每一条边
    for _ in range(m):
        u = int(input[ptr])
        ptr += 1
        v = int(input[ptr])
        ptr += 1
        w = int(input[ptr])
        ptr += 1
        c = int(input[ptr])
        ptr += 1
        if c == 0:
            uf.union(u, v)  # 如果不是红色边，直接合并
        else:
            red_edges.append((u, v, w))  # 如果是红色边，存储
            sum_red += w

    # 初始连通块数
    C0 = uf.count

    # 对红色边按权值从小到大排序
    red_edges.sort(key=lambda x: x[2])

    # 存储在连通块数不超过k时，最大可以得到的权值
    min_retained = [0]
    sum_retained = 0
    for u, v, w in red_edges:
        root_u = uf.find(u)
        root_v = uf.find(v)
        if root_u != root_v:  # 如果u和v不在同一个连通块
            uf.union(root_u, root_v)  # 合并它们
            sum_retained += w  # 增加红色边的权值
            min_retained.append(sum_retained)
            if len(min_retained) - 1 == C0 - 1:
                break  # 合并到连通块数只剩下一个时停止

    # 输出结果
    for k in range(1, n + 1):
        if k >= C0:
            print(sum_red, end=" ")
        else:
            t_needed = C0 - k
            print(sum_red - min_retained[t_needed], end=" ")

if __name__ == "__main__":
    main()

Java 代码

import java.util.*;

public class Main {
    static class UnionFind {
        int[] parent, rank;
        int count;

        public UnionFind(int size) {
            parent = new int[size + 1];
            rank = new int[size + 1];
            for (int i = 1; i <= size; i++) {
                parent[i] = i;
            }
            count = size;
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public boolean union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return false;
            }
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                if (rank[rootX] == rank[rootY]) {
                    rank[rootX]++;
                }
            }
            count--;
            return true;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        UnionFind uf = new UnionFind(n);
        long sumRed = 0;
        List<int[]> redEdges = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            int c = sc.nextInt();
            if (c == 0) {
                uf.union(u, v);
            } else {
                redEdges.add(new int[] {u, v, w});
                sumRed += w;
            }
        }

        int C0 = uf.count;
        redEdges.sort(Comparator.comparingInt(a -> a[2]));

        List<Long> minRetained = new ArrayList<>();
        long sumRetained = 0;
        minRetained.add(0L);

        for (int[] edge : redEdges) {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            int rootU = uf.find(u);
            int rootV = uf.find(v);
            if (rootU != rootV) {
                uf.union(rootU, rootV);
                sumRetained += w;
                minRetained.add(sumRetained);
                if (minRetained.size() - 1 == C0 - 1) {
                    break;
                }
            }
        }

        for (int k = 1; k <= n; k++) {
            if (k >= C0) {
                System.out.print(sumRed + " ");
            } else {
                int tNeeded = C0 - k;
                System.out.print(sumRed - minRetained.get(tNeeded) + " ");
            }
        }
    }
}

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class UnionFind {
public:
    vector<int> parent, rank;
    int count;

    UnionFind(int size) {
        parent.resize(size + 1);
        rank.resize(size + 1, 0);
        for (int i = 1; i <= size; i++) {
            parent[i] = i;
        }
        count = size;
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    bool unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return false;
        }
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            if (rank[rootX] == rank[rootY]) {
                rank[rootX]++;
            }
        }
        count--;
        return true;
    }
};

int main() {
    int n, m;
    cin >> n >> m;

    UnionFind uf(n);
    long long sumRed = 0;
    vector<tuple<int, int, int>> redEdges;

    for (int i = 0; i < m; i++) {
        int u, v, w, c;
        cin >> u >> v >> w >> c;
        if (c == 0) {
            uf.unionSet(u, v);
        } else {
            redEdges.push_back({u, v, w});
            sumRed += w;
        }
    }

    int C0 = uf.count;
    sort(redEdges.begin(), redEdges.end(), [](const tuple<int, int, int>& a, const tuple<int, int, int>& b) {
        return get<2>(a) < get<2>(b);
    });

    vector<long long> minRetained = {0};
    long long sumRetained = 0;
    for (auto& edge : redEdges) {
        int u = get<0>(edge);
        int v = get<1>(edge);
        int w = get<2>(edge);
        int rootU = uf.find(u);
        int rootV = uf.find(v);
        if (rootU != rootV) {
            uf.unionSet(rootU, rootV);
            sumRetained += w;
            minRetained.push_back(sumRetained);
            if (minRetained.size() - 1 == C0 - 1) {
                break;
            }
        }
    }

    for (int k = 1; k <= n; k++) {
        if (k >= C0) {
            cout << sumRed << " ";
        } else {
            int tNeeded = C0 - k;
            cout << sumRed - minRetained[tNeeded] << " ";
        }
    }
    return 0;
}

题目内容

小红有一张由 $n$ 个节点、$m$ 条边构成的图，每一条边都有一个权值，其中部分边被染成了红色，这些边是可以被删除的。对于每条染成红色的边，如果删除它，可以获得这条边的权值。

请你求出，对于每个 $k(1≤k≤n)$，在最终图的连通块数量不超过 $k$ 的条件下，小红最多能够获得的权值总和是多少。请依次输出 $k = 1,2,...,n$ 时的结果。

对于图上的两个点，如果它们之间有边相连，则称他们位于同一个连通块里。

输入描述

第一行包含两个整数 $n$ 和 $m(1 ≤ n,m ≤10^5)$，分别表示图中节点和边的数量。节点编号为 $1$ 到 $n$。 接下来 $m$ 行，第 $i$ 行输入四个整数

$u_i,v_i,w_i,c_i(1≤u_i,u_i≤n;1≤w_i<10^9;0≤c_i≤1)$代表第 $i$ 条边连接节点 $u_i$ 和 $v_i$，这条边的权值为 $w_i$ ，其中 $c_i= 1$ 表示该边被染成红色，$c_i=0$ 表示该边未被染色。

保证图中没有自环和重边，图初始是连通的。

输出描述

在一行上输出 $n$ 个整数，其中，第 $i$ 个整数代表当要求最终图的连通块数量小于等于 $i$ 时，小红最多能够获得的受益总和。

样例1

输入

4 4
1 2 5 1
2 3 3 0
3 4 4 1
1 4 2 1

输出

5 9 11 11

说明

删除第一条边，连通块数量为 $1$ ，权值总和为 $5$ 。

再删除第三条边，连通块数量为 $2$ ，权值总和为 $9$ 。

再删除第四条边，连通块数量为 $3$ ，权值总和为 $11$ 。

第二条边没有被染红，所以不会被删除。