#P3624. [Apio2008]免费道路

    ID: 1781 传统题 2000ms 128MiB 尝试: 2469 已通过: 676 难度: 6 上传者: 标签>难度分类提高图论Kruskal数据结构普通并查集构造与建模图构造CF1900

[Apio2008]免费道路

[APIO2008] 免费道路

题目描述

新亚王国有 NN 个村庄,由 MM 条道路连接。道路分为鹅卵石路和水泥路。维持道路免费通行需要花钱,国王决定只保留尽可能少的免费道路,同时保证任意两个不同村庄之间恰有一条由免费道路组成的路径。国王还要求免费道路中恰有 KK 条鹅卵石路。

例如,图 1(a) 给出了五个村庄之间的道路。若 K=2K=2,可以留下连接 (1,2)(1,2)、(2,3)(2,3)、(3,4)(3,4) 和 (3,5)(3,5) 的四条道路,如图 1(b)。其中 (2,3)(2,3) 和 (3,4)(3,4) 是鹅卵石路。

原赛图 1,左为全部道路,右为一组免费道路

图中的实线表示水泥路,虚线表示鹅卵石路。图 1(b) 只画出了免费的道路。

给定道路及 KK,判断是否存在符合要求的方案。若有,请输出任意一个方案。

输入格式

第一行三个整数 N,M,KN,M,K。

接下来 MM 行,第 ii 行用三个整数 ui,vi,ciu_i,v_i,c_i 描述一条连接村庄 uiu_i 与 viv_i 的道路。村庄编号为 11 至 NN。ci=0c_i=0 表示鹅卵石路,ci=1c_i=1 表示水泥路。任意一对村庄之间至多有一条道路。

输出格式

无解时输出一行 no solution。

有解时,逐行输出保留的每条道路,每行复用该道路在输入中的三个整数及其顺序。各行顺序任意。

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

数据范围与评分

1≤N≤200001\le N\le 20000,1≤M≤1000001\le M\le 100000,0≤K≤N−10\le K\le N-1。

每个测试情形独立判定,正确得该情形的满分。原赛有 2020 分的数据满足 K≤10K\le 10。