Description:


从前一个和谐的班级,有 nl 个是男生,有 nr 个是女生。编号分别为 1,…,nl 和 1,…,nr。
有若干个这样的条件:第 v 个男生和第 u 个女生愿意结为配偶。
请问这个班级里最多产生多少对配偶?

Input:


第一行三个正整数,nl,nr,m。
接下来 m 行,每行两个整数 v,u 表示第 v 个男生和第 u 个女生愿意结为配偶。保证 1≤v≤nl,1≤u≤nr,保证同一个条件不会出现两次。

Output:


第一行一个整数,表示最多产生多少对配偶。
接下来一行 nl 个整数,描述一组最优方案。第 v 个整数表示 v 号男生的配偶的编号。如果 v 号男生没配偶请输出 0。

Sample Input:


Sample Output:


Explanation:


1 号男生跟 2 号女生幸福地生活在了一起~
2 号男生跟 1 号女生幸福地生活在了一起~

题解:


作为二分图匹配模板题,还是用来各种方法做的~~

一、匈牙利算法(DFS实现)

二分图匹配最简单的算法,直接找增广路。
Time:1446ms

二、匈牙利算法(BFS实现)

如果把匈牙利算法用BFS实现,时间会降到800ms~1000ms,然而我没有去写~~

三、最大流

二分图匹配还可以用最大流来做,建立一个源点s和汇点t,s向每一个x方点连一条容量为1的边,每一个y方点向汇点连一条容量为1的边。
直接用isap一遍最大流。
Time: 298ms

四、Hopcroft-Karp算法

这是针对二分图匹配的较快的一种算法,过程和Dinic十分相似,我们每次把所有x方未盖点放进队列,进行BFS找到一棵匈牙利树,具体实现见代码。
然后对每一个未盖点进行DFS对所有的增广路将link接起来。
优化:
1. 由于BFS是按照距离远近搜索,设第一次路径长度为dis,则我们限制以后找到的增广路长度等于dis,其实貌似也快不了多少
2. 读入是若两点均为未盖点,贪心地将它们先匹配。
3. 对于每一个未盖点进行DFS是不必每次清空vis数组,这样还可以防止对于y方点到x方点走错。
4. 玄学的getchar_unlocked

Time: 41ms