1013. 彩色匹配

题目描述

给定一个二分图 G = (L, R, E)，其左右两部各有 n 个点，之间有 m条边，每条边被染成蓝色或红色。一个完美匹配是 n 条两两没有公共端点的边，使得每个左部点和每个右部点都恰好被匹配一次。请你找出一组完美匹配，使得其中恰好有 k 条红边。

输入格式

本题有多组测试数据。第一行输入一个整数 T (1 ≤ T ≤ 60)，表示测试数据组数。接下来按如下格式输入 T 组数据：第一行输入三个整数 n, m, k (1 ≤ n ≤ 120, 0 ≤ m ≤ n2, 0 ≤ k ≤ n)，表示二分图左右两部各自的点数、图的总边数，以及完美匹配中要求的红边数。随后 m 行，每行输入三个整数 u, v, c (1 ≤ u, v ≤ n, c ∈ {0, 1})，表示左部点 Lu 与右部点 Rv 之间有一条边。

• c = 0 表示蓝边；

• c = 1 表示红边。

保证同一组数据中不会出现 u, v 均相同的两条边，至多 10 组数据

n > 50。

输出格式

本题使用 Special Judge 进行评测。

对于每组数据，输出一行。如果不存在红边数恰好为 k 的完美匹配，输出 -1。否则，输出 n 个用空格分隔的整数 p1, p2, …, pn，其中 pi 表示左部

点 Li 与右部点 Rpi 匹配。

输出必须满足：

• pi 均为 1 到 n 之间的整数，且两两不同。

• 对于所有 i，边 (Li, Rpi ) 存在。

• 恰好有 k 条被选中的边为红边。

样例输入

3
2 4 1
1 1 1
1 2 0
2 1 0
2 2 0
2 2 2
1 1 1
2 2 1
2 2 1
1 1 0
2 2 0

样例输出

1 2
1 2
-1

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第1场）