#P14474. [2025年广东省队集训]最小生成树

    ID: 13691 传统题 2000ms 1024MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500动态规划最小生成树图论排序状压DP枚举

[2025年广东省队集训]最小生成树

问题描述

给定一张 nn 个点 mm 条边的 无向连通图,图中的第 ii 条边有 ai,bia_i,b_i 两个权重。

对于图中的每条边,你可以选择 ai,bia_i,b_i 其中之一作为该条边的边权。

对于所有满足 0≤k≤m0\le k\le m 的整数 kk,你需要求出,若选择 恰好 kk 个 aia_i 作为对应边的边权,恰好 m−km-k 个 bib_i 作为对应边的边权,该图的最小生成树的边权和 最大 是多少。

输入格式

第一行包含两个整数 n,mn,m。

接下来 mm 行,每行包含四个整数 xi,yi,ai,bix_i,y_i,a_i,b_i,表示图中的第 ii 条边,其连接 xi,yix_i,y_i 两点,权重为 ai,bia_i,b_i。

输出格式

输出 m+1m+1 行共 m+1m+1 个整数,第 ii 个数表示 k=i−1k=i-1 时的答案。

输入样例1

3 3
1 2 5 4
2 3 2 9
1 3 3 6

输出样例1

10
11
8
5

样例1解释

k=0k=0:选择 b1,b2,b3b_1,b_2,b_3,最小生成树边权和为 b1+b3=10b_1+b_3=10。

k=1k=1:选择 a1,b2,b3a_1,b_2,b_3,最小生成树边权和为 a1+b3=11a_1+b_3=11。

k=2k=2:选择 a1,b2,a3a_1,b_2,a_3,最小生成树边权和为 a1+a3=8a_1+a_3=8。

k=3k=3:选择 a1,a2,a3a_1,a_2,a_3,最小生成树边权和为 a2+a3=5a_2+a_3=5。

数据范围

对于所有数据,保证 2≤n≤92\le n\le 9,n−1≤m≤100n-1\le m\le 100,1≤xi,yi≤n1\le x_i,y_i\le n,1≤ai,bi≤1081\le a_i,b_i\le 10^8。保证图连通且无自环。

测试点编号 n≤n\leq m≤m\leq
1∼41\sim 4 66 1818
5∼65\sim 6 3030
7∼87\sim 8 100100
9∼109\sim 10 77 3030
11∼1211\sim 12 100100
13∼1413\sim 14 88 3030
15∼1615\sim 16 100100
17∼1817\sim 18 99 3030
19∼2019\sim 20 6060
21∼2521\sim 25 100100