#P3559. [Ctsc2014]图的分割
[Ctsc2014]图的分割
[CTSC2014] 图的分割
题目描述
给定连通无向图 。每条边 的权值 是正整数,图中没有重边和自环。路径是相邻顶点之间都有边的顶点序列。连通指任意两个顶点间都有路径。
对于 , 是 中两端均属于 的边集。图 称为 的诱导子图,它的边权沿用 中的原权值。
对任意连通图 ,定义 为以下边的集合。若删除 中权值严格大于一条边自身权值的所有边后, 仍连通,则该边属于 。如果 的诱导子图 连通且 ,定义
若 ,定义 。这里 表示 的顶点数。
的一个分割 由 个非空、两两不交的顶点集组成,它们的并集是 ,且每个 的诱导子图都连通。称 为分割的度。对两个不同的块,定义
$$D(C_i,C_j)= \min_{\substack{(u,v)\in E\\u\in C_i,\ v\in C_j}} w_G(u,v).$$若没有连接两块的边,取 。
给定正整数序列 。若对任意 都有
$$D(C_i,C_j)>\min\bigl(M(C_i)+Z[|C_i|],\,M(C_j)+Z[|C_j|]\bigr),$$则称该分割为半完美分割。若该分割半完美,并且每个 的诱导子图均不存在度大于 的半完美分割,则称它为完美分割。对诱导子图再次判断时,相关量均在所考察的诱导子图内计算,仍用同一个 序列。
请给出 的一个完美分割。
输入格式
第一行两个正整数 ,表示顶点数和边数。第二行有 个正整数 。
接下来 行,每行三个正整数 ,表示连接顶点 的无向边,权值为 。
输出格式
第一行一个正整数 ,表示分割的度。随后 行,每行先给出该块的顶点数 ,再给出 个顶点编号。
样例 #1
5 6
3 3 2 2 1
1 2 3
1 3 5
1 4 6
2 4 10
2 5 5
4 5 8
4
2 1 2
1 3
1 4
1 5
样例使用 BZOJ 归档中可运行的版本。原 PDF 的同一示例末尾还列出了两条引用顶点 的边,但示例只有 个顶点。
补充样例 #2
3 2
2 1 1
1 2 1
2 3 5
2
2 1 2
1 3
数据范围
,,。给出的无向图连通,无重边和自环。
| 原赛累计分值 | 条件 |
|---|---|
| , | |
| , |