1204: 征兵
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：1
Solved：0
Description
一个国王,他拥有一个国家。最近他因为国库里钱太多了,闲着要征集一只部队要保卫国家。他选定了 N 个女兵和 M 个男
兵,但事实上每征集一个兵他就要花 10000RMB,即使国库里钱再多也伤不起啊。他发现,某男兵和某女兵之间有某种关系(往正常方面想,一共 R 种关系),这种关系可以使 KING 少花一些钱就可以征集到兵,不过国王也知道,在征兵的时候,每一个兵只能使用一种关系来少花钱。这时国王向你求助,问他最少要花多少的钱。
兵,但事实上每征集一个兵他就要花 10000RMB,即使国库里钱再多也伤不起啊。他发现,某男兵和某女兵之间有某种关系(往正常方面想,一共 R 种关系),这种关系可以使 KING 少花一些钱就可以征集到兵,不过国王也知道,在征兵的时候,每一个兵只能使用一种关系来少花钱。这时国王向你求助,问他最少要花多少的钱。
Input
第一行:T,一共 T 组数据。
接下来 T 组数据,
第一行包括 N,M,R
接下来的 R 行 包括 Xi,Yi,Vi 表示如果招了第 Xi 个女兵,再招第 Yi 个男兵能省 Vi 元(同样表示如果招了第 Yi 个男兵,再招第 Xi 个女兵能也省 Vi 元)
接下来 T 组数据,
第一行包括 N,M,R
接下来的 R 行 包括 Xi,Yi,Vi 表示如果招了第 Xi 个女兵,再招第 Yi 个男兵能省 Vi 元(同样表示如果招了第 Yi 个男兵,再招第 Xi 个女兵能也省 Vi 元)
Output
共 T 行,表示每组数据的最终花费是多少。
Sample Input Copy
2
5 5 8
4 3 6831
1 3 4583
0 0 6592
0 1 3063
3 3 4975
1 3 2049
4 2 2104
2 2 781
5 5 10
2 4 9820
3 2 6236
3 1 8864
2 4 8326
2 0 5156
2 0 1463
4 1 2439
0 4 4373
3 4 8889
2 4 3133Sample Output Copy
71071
54223HINT
数据范围
数据保证 T<=5 , m,n<=10000, r<=50000, Xi<=m, Yi<=n,Vi<=10000, 结果<=2^31-1
数据保证 T<=5 , m,n<=10000, r<=50000, Xi<=m, Yi<=n,Vi<=10000, 结果<=2^31-1