「NOIP模拟赛」征兵

2014年7月3日3,7780

一个国王,他拥有一个国家。最近他因为国库里钱太多了,闲着蛋疼要征集一只部队要保卫国家。他选定了N个女兵和M个男兵,但事实上每征集一个兵他就要花10000RMB,即使国库里钱再多也伤不起啊。他发现,某男兵和某女兵之间有某种关系(往正常方面想,一共R种关系),这种关系可以使KING少花一些钱就可以征集到兵,不过国王也知道,在征兵的时候,每一个兵只能使用一种关系来少花钱。这时国王向你求助,问他最少要花多少的钱。

读入(conscription.in)

第一行:T,一共T组数据。

接下来T组数据,

第一行包括N,M,R

接下来的R行 包括Xi,Yi,Vi 表示如果招了第Xi个女兵,再招第Yi个男兵能省Vi元(同样表示如果招了第Yi个男兵,再招第Xi个女兵能也省Vi元)

输出(conscription.out)

共T行,表示每组数据的最终花费是多少(因为国库里的钱只有2^31-1,所以保证最终花费在maxlongint范围内)

样例输入

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 3133

样例输出

71071

54223

数据范围

数据保证T<=5 ,m,n<=10000,r<=50000,Xi<=m,Yi<=n,Vi<=10000,结果<=2^31-1

直接最大生成树不解释

 

avatar
  Subscribe  
提醒