#P18417. Greedy Bipartite Matching
Greedy Bipartite Matching
Greedy Bipartite Matching
标准输入、标准输出。
给定一个有 个顶点的带权二部图,左右两侧各有 个顶点,两侧顶点分别编号为 到 。
称一个匹配为贪心匹配,当且仅当:在所有匹配中,它包含的权值为 的边最多;在满足此前条件的匹配中,它包含的权值为 的边最多;在继续满足此前全部条件的匹配中,它包含的权值为 的边最多;依此类推。也就是把匹配中各权值的边数按权值从小到大组成向量,使这个向量按字典序最大。
图会逐批加入边。请在加入每批边后,求当前图的贪心匹配的大小(边数)。
输入格式
第一行包含两个非负整数 (,),分别表示二部图每侧的顶点数和不同边权的个数。
接下来有 个块。第 个块先给出一个非负整数 ,表示权值为 的边数。随后 行,每行两个整数 (),表示在左侧顶点 和右侧顶点 之间加入一条边。
保证 。
两个顶点之间可以有多条边,包括同权和不同权的重边。
输出格式
在一行中输出 个整数:依次表示仅考虑权值不超过 的边时,贪心匹配的大小。
时没有需要输出的整数,允许输出为空。 时所有 必须为 。
样例
3 4
2
1 1
1 2
2
1 1
2 2
2
1 3
3 2
1
3 3
1 2 2 3