#P3559. [Ctsc2014]图的分割

    ID: 2678 传统题 1000ms 128MiB 尝试: 93 已通过: 50 难度: 9 上传者: 标签>难度分类省选/NOI-贪心排序贪心数据结构普通并查集路径压缩按大小合并CF2600

[Ctsc2014]图的分割

[CTSC2014] 图的分割

题目描述

给定连通无向图 G=(V,E)G=(V,E)。每条边 (u,v)(u,v) 的权值 wG(u,v)w_G(u,v) 是正整数,图中没有重边和自环。路径是相邻顶点之间都有边的顶点序列。连通指任意两个顶点间都有路径。

对于 C⊆VC\subseteq V,EG(C)E_G(C) 是 GG 中两端均属于 CC 的边集。图 (C,EG(C))(C,E_G(C)) 称为 CC 的诱导子图,它的边权沿用 GG 中的原权值。

对任意连通图 HH,定义 S(H)S(H) 为以下边的集合。若删除 HH 中权值严格大于一条边自身权值的所有边后,HH 仍连通,则该边属于 S(H)S(H)。如果 CC 的诱导子图 HH 连通且 ∣C∣>1|C|>1,定义

M(C)=min⁡(u,v)∈S(H)wG(u,v).M(C)=\min_{(u,v)\in S(H)} w_G(u,v).

若 ∣C∣=1|C|=1,定义 M(C)=0M(C)=0。这里 ∣C∣|C| 表示 CC 的顶点数。

GG 的一个分割 (C1,…,Ck)(C_1,\ldots,C_k) 由 kk 个非空、两两不交的顶点集组成,它们的并集是 VV,且每个 CiC_i 的诱导子图都连通。称 kk 为分割的度。对两个不同的块,定义

$$D(C_i,C_j)= \min_{\substack{(u,v)\in E\\u\in C_i,\ v\in C_j}} w_G(u,v).$$

若没有连接两块的边,取 D(Ci,Cj)=+∞D(C_i,C_j)=+\infty。

给定正整数序列 Z[1],…,Z[n]Z[1],\ldots,Z[n]。若对任意 1≤i<j≤k1\le i<j\le k 都有

$$D(C_i,C_j)>\min\bigl(M(C_i)+Z[|C_i|],\,M(C_j)+Z[|C_j|]\bigr),$$

则称该分割为半完美分割。若该分割半完美,并且每个 CiC_i 的诱导子图均不存在度大于 11 的半完美分割,则称它为完美分割。对诱导子图再次判断时,相关量均在所考察的诱导子图内计算,仍用同一个 ZZ 序列。

请给出 GG 的一个完美分割。

输入格式

第一行两个正整数 n,mn,m,表示顶点数和边数。第二行有 nn 个正整数 Z[1],…,Z[n]Z[1],\ldots,Z[n]。

接下来 mm 行,每行三个正整数 u,v,wu,v,w,表示连接顶点 u,vu,v 的无向边,权值为 ww。

输出格式

第一行一个正整数 kk,表示分割的度。随后 kk 行,每行先给出该块的顶点数 tt,再给出 tt 个顶点编号。

样例 #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 的同一示例末尾还列出了两条引用顶点 66 的边,但示例只有 55 个顶点。

补充样例 #2

3 2
2 1 1
1 2 1
2 3 5
2
2 1 2
1 3

数据范围

1≤u,v≤n1\le u,v\le n,u≠vu\ne v,1≤Z[i],w≤1091\le Z[i],w\le10^9。给出的无向图连通,无重边和自环。

原赛累计分值 条件
10%10\% n=2n=2
30%30\% n≤10n\le10
60%60\% n≤500n\le500,m≤2000m\le2000
100%100\% n≤100000n\le100000,m≤500000m\le500000