题目描述
温迪有一个国家，他想建立一支军队来保护他的国家。他收留了N个女孩和M个男孩，想把她们收留成他的士兵。征兵无特权，必须交纳一万元。女孩和男孩之间有一些关系，温迪可以利用这些关系来降低他的成本。如果X女孩和Y男孩有D关系，并且其中一个已经被收集，Windy可以用10000-D人民币收集另一个。现在考虑到男孩和女孩之间的所有关系，你的任务是找到风必须支付的最少的钱。注意，收集一个士兵时只能使用一个关系。Input
输入的第一行是测试用例的数量。 每个测试用例的第一行包含三个整数，n、m和r。 然后R行，每个包含三个整数Xi，Yi和DI。 每个测试用例前都有一个空白行。
1 ≤ N, M ≤ 10000
0 ≤ R ≤ 50,000
0 ≤ x < N
0 ≤ y < M
0 < d < 10000
Output
For each test case output the answer in a single line.
Sample Input
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
Sample Output
71071
54223
代码如下，参考挑战程序设计竞赛
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
#define ull unsigned long long
#define ll long long
const int maxn=5e4+;
int par[maxn];
int rank1[maxn],n,m,r; void init(int n) //初始化
{
for(int i=;i<n;i++)
{
par[i]=i;
rank1[i]=;
}
}
int find(int x)
{
if(par[x]==x)
{
return x;
}
else
{
return par[x]=find(par[x]);
}
}
void unite(int x,int y)
{
x=find(x);
y=find(y);
if(x==y)
return ;
if(rank1[x]<rank1[y])
{
par[x]=y;
}
else
{
par[y]=x;
}
if(rank1[x]==rank1[y])
rank1[x]++;
}
struct edge{
int x,y,cost;
}e[];
bool cmp(const edge e1,const edge e2)
{
return e1.cost<e2.cost;
}
ll kruskal()
{
ll res=;
sort(e+,e+r+,cmp);
for(int i=;i<=r;i++)
{
edge e1=e[i];
if(find(e1.x)!=find(e1.y))
{
unite(e1.x,e1.y);
res=res+e1.cost;
}
}
return res;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&r);
init(n+m);
for(int i=;i<=r;i++)
{
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].cost);
e[i].cost=-e[i].cost;
e[i].y=e[i].y+n;
}
printf("%lld\n",10000LL*(n+m)+kruskal());
}
return ;
}