[GDKOI2024 提高组] 匹配

Luogu

IDLGP10080

Time1000ms

Memory512MB

DifficultyP6

2024广东Special JudgeO2优化广度优先搜索 BFS深度优先搜索 DFS二分图

给定一个 $2n$ 个点 $m$ 条边的二分图，左部点编号为 $1 \sim n$，右部点编号为 $n + 1 \sim 2n$。给定每条边为黑色或白色，你需要找到一个完美匹配，使得匹配里的黑色边数恰好为偶数。如果你对二分图的定义有疑问： - 二分图是一个无向图，点分为左右两部分，每部分各 $n$ 个点，每条边都连接两个属于不同部分的点。 - 一个完美匹配是一个大小为 $n$ 的边的集合，使得每个点都恰好与集合里的一条边相连。 ## Input 第一行一个正整数 $T$，表示数据组数。每组数据的格式如下：第一行两个正整数 $n, m$，表示图的点数和边数。接下来 $m$ 行，每行三个整数 $u_i, v_i, c_i(1 \leq u_i \leq n, n+1 \leq v_i \leq 2n, 0 \leq c_i \leq 1)$，表示一条连接 $u_i$, $v_i$ 的边，颜色为 $c_i$。$c_i = 0$ 表示白色，$c_i = 1$ 表示黑色。 ## Output 对于每组数据：如果无解，输出一行 $-1$。否则，输出一行 $n$ 个正整数，表示你找到的完美匹配里每条边的编号。边按照输入顺序编号为 $1 \sim m$。 [samples] ## Note **【样例解释】** 在第一组数据中，一个合法的完美匹配是 $(1, 6),(2, 5),(3, 4)$，且里面有恰好两条黑色边。在第二组数据中，虽然存在完美匹配，但每个完美匹配都有奇数条黑色边。 **【数据范围】** **本题使用子任务捆绑测试。** 对于所有数据，保证 $1 \leq T \leq 250$，$2 \leq n,\sum n \leq 500$，$1 \leq m \leq n^2$。保证图中不存在重边，即对于 $i \neq j$ 有 $(u_i, v_i)\neq (u_j , v_j)$。 - Subtask 1（20%）：$n ≤ 8$，$T ≤ 10$。 - Subtask 2（20%）：$n ≤ 18$，$T ≤ 10$。 - Subtask 3（20%）：$c_i$ 在 $\{0, 1\}$ 里独立均匀随机。 - Subtask 4（40%）：无特殊限制。

Samples

Input #1

Output #1

5 3 6
-1

API Response (JSON)

{
  "problem": {
    "name": "[GDKOI2024 提高组] 匹配",
    "description": {
      "content": "给定一个 $2n$ 个点 $m$ 条边的二分图，左部点编号为 $1 \\sim n$，右部点编号为 $n + 1 \\sim 2n$。 给定每条边为黑色或白色，你需要找到一个完美匹配，使得匹配里的黑色边数恰好为偶数。 如果你对二分图的定义有疑问： - 二分图是一个无向图，点分为左右两部分，每部分各 $n$ 个点，每条边都连接两个属于不同部分的点。 - 一个完美匹配是一个大小为 $n$ 的边的集合",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10080"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个 $2n$ 个点 $m$ 条边的二分图，左部点编号为 $1 \\sim n$，右部点编号为 $n + 1 \\sim 2n$。\n\n给定每条边为黑色或白色，你需要找到一个完美匹配，使得匹配里的黑色边数恰好为偶数。\n\n如果你对二分图的定义有疑问：\n\n- 二分图是一个无向图，点分为左右两部分，每部分各 $n$ 个点，每条边都连接两个属于不同部分的点。\n- 一个完美匹配是一个大小为 $n$ 的边的集合...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments