#P17702. [2026年江苏省队集训]众
[2026年江苏省队集训]众
题面描述
给定一张由 个左部点和 个右部点组成的,包含 条边的简单二分图。
定义一组匹配为点对 满足 和 是左部点, 是右部点,且 和 均与 有边相连。
求图的最大匹配大小。换句话说,找到尽量多组匹配,满足任意两组匹配不共用顶点。无需输出方案。
输入格式
输入的第一行包含一个正整数 ,表示测试数据组数。
每组测试数据的第一行包含三个非负整数 。
接下来 行每行包含两个整数 ,表示一条连接第 个左部点和第 个右部点的边。
输出格式
输出 行每行一个整数,表示最大匹配的大小。
样例输入与输出
1
6 3 10
3 1
4 1
1 2
2 2
3 2
4 2
5 2
6 2
3 3
4 3
2
样例解释
一种方案是选择 和 两组匹配。
数据范围与子任务
对于所有数据,满足 ,,,。
| 子任务编号 | 子任务分值 | 特殊性质 |
|---|---|---|
| 所有右部点的度数均为 | ||
| 每条边的端点在所有点中均匀随机 | ||
| 无特殊限制 |
其中子任务 的随机方式为:每条边不断均匀随机端点编号直到该边没有出现过。