Description:


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

Input:


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

Output:


第一行一个整数,表示幸福程度之和的最大值。
接下来一行 nl 个整数,描述一组最优方案。第 v 个整数表示 v 号男生的配偶的编号。如果 v 号男生没配偶请输出 0。

Sample Input:


Sample Output:


题解:


虽说是模板题但还是不能够直接用KM算法的。
由于两边人数不同,我们需要将人数补齐,然后不存在的边视为边权为0的边。
再上KM算法。
奈何数据太强,不能够直接去DFS,用BFS才可以过所有的点。
getchar_unlocked()大法好~~~