#288. 舞动的夜晚
舞动的夜晚
题目描述
给定一个二分图,求哪些边不可能出现在任何最大匹配中。等价地,强制选择这样的边会使可选匹配的最大规模变小。
输入格式
首行 N、M、T,左右两部分的大小及边数;随后 T 行 x、y,边按输入顺序从1编号。
输出格式
先输出这些边的数量 cnt;再按编号升序输出 cnt 个边编号,cnt=0 时仍输出空行。
样例输入
3 3 6
1 1
2 1
2 2
3 1
3 2
3 3
样例输出
3
2 4 5
题意整理;原题与输入输出格式对照。
给定一个二分图,求哪些边不可能出现在任何最大匹配中。等价地,强制选择这样的边会使可选匹配的最大规模变小。
首行 N、M、T,左右两部分的大小及边数;随后 T 行 x、y,边按输入顺序从1编号。
先输出这些边的数量 cnt;再按编号升序输出 cnt 个边编号,cnt=0 时仍输出空行。
3 3 6
1 1
2 1
2 2
3 1
3 2
3 3
3
2 4 5
题意整理;原题与输入输出格式对照。