[Ctsc2014]图的分割

时间限制:10s      空间限制:128MB

题目描述


输入格式

 输入的第一行包含两个正整数n,m,表示输入的无向图有n个顶点,m条无向边。
第二行包含两个正整数Z[1],Z[2],...,Z[n](Z[i]≤10^9)。
下面m行,每行三个正整数u,v,w(1≤u,v≤n,u≠v,w≤10^9),表示图中存在一条边(u,v)且权值为w。输入的无向图保证没有重边和自环。


输出格式

输出包含k+1行,第一行包含一个正整数k,表示你给出的分割的度。
下面k行,每行描述一个C。每行一开始包含一个正整数t,表示|Ci|,然后跟着t个不超过n的正整数,表示C中的顶点编号。


样例输入

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

提示

对于10%的数据,满足n=2
对于30%的数据,满足n≤10
对于60%的数据,满足n≤500,m≤2000
对于100%的数据,满足n≤100000,m≤500000



题目来源

没有写明来源

Menuappsclose