问题 3969 --还是老余

3969: 还是老余

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

上一题过后,老余心里打着自己的算盘,成的对数最多还是比较好的,总幸福度最大可能就没老余的份了,所以老余想让对数最多,但最多的对数的情况可能有多种,每种情况都有幸福度最大的一对和幸福度最小的一对,老余想取所有情况中相差的最小的那种情况,输出最小差别

输入

Case,每个Case第一行,NMK表示N个男生,M个女生,K个关系。接下来的K行,每行输入三个数,u,v,w表示第u个男生与第v个女生在一起的幸福度为w,保证每个男生与女生间只有一个幸福度。1<=NM<=1000<K<M*N0<w<=100

输出

Case输出一行,一个整数,表示最小的幸福度差

样例输入

3 4 10
1 2 3
1 1 4
2 3 5
1 3 2
2 4 5
3 4 2
2 1 7
3 2 6
3 3 1
3 1 8

样例输出

2

提示

最多3对,取的对为1 1 4  2 3 5  3 2 6时最大的幸福度减最小的幸福度最小,为2

来源

 

[提交][状态]