题目
Windy有一个国家,他想建立一支军队来保护他的国家。他已经挑选了N个女孩和M个男孩,想要收集他们成为他的士兵。无任何特权征召一名士兵,必须支付一万元。女孩和男孩之间有一些关系Windy可以利用这些关系来降低他的成本。如果女孩x和男孩y有恋爱关系,其中一个已经被收集,Windy可以用10000元人民币去收集另一个。考虑到女孩和男孩之间的关系,你的任务是找到Windy需要支付的最少的钱。注意,当收集一个士兵时,只能使用一种关系。
输入数据形式
输入
第一行输入是测试用例的数量。
每个测试用例的第一行包含三个整数,N, M和R。
接下来是R行,每一行包含三个整数xi yi di。
在每个测试用例之前有一个空白行。
输出数据形式
输出:
对于每个测试用例,答案输出在一行中。
输入数据范围:
1≤n, m≤10000
0≤r≤50,000
0≤xi < N
0≤yi < M
0 < di < 10000
知识点1:
当题目求解求深林的最大权值和时(可以权值既有正数又有负数的情况下),可以转化为求最小生成树的问题:
将这些边的权值全部取反(即取负),用最小生成树的形式求解的就是最小值,也就是-1 * (最大深林权值和)
知识点2:
我一直以为kruskal()算法是求一颗树的情况下的最小生成树问题。然而实际上,它同样也可以求深林所组成的多个最小生成树的问题。
思路:
某征集一个人,则费用为10000 - (已经征募的人中和此人最大的亲密度)
所以想要花费的费用少,则亲密度要高。
此题的过程是不断的一个接一个的将人员,放入到征募的集合中。又征募集合外的人所需要的费用就是10000 - 征募集合外的人到集合内所有人中最大的亲密度。
所以可以看出,此题可以建立成求最大生成树的问题。当为最大生成树的时候,所消耗的费用则最少。
而最大生成树,则可以将权值全部取反(即取负),然后求最小生成树。得到的最小生成树就是-1 * (最大生成树)了
代码实现:
/*
每颗树,都可以用最小生成树的方式求出它对应的最小消耗。
然后将每棵树的消耗加起来即可
*/
# include <iostream>
# include <algorithm>
# include <cstring>
using namespace std;
const int N = 20010 , R = 50010;
int p[N];
struct Node
{
int a,b,w;
}edgs[R];
int cmp(struct Node p , struct Node t)
{
return p.w < t.w;
}
int to_find(int x)
{
if(x != p[x])
{
p[x] = to_find(p[x]);
}
return p[x];
}
int n,m,r;
int main()
{
int loop;
scanf("%d",&loop);
while(loop--)
{
scanf("%d %d %d",&n,&m,&r);
for(int i = 0 ; i <= n + m; i++)
{
p[i] = i;
}
for(int i = 1; i <= r ; i++)
{
scanf("%d%d%d",&edgs[i].a,&edgs[i].b,&edgs[i].w);
edgs[i].b += n;
edgs[i].w *= -1;
}
sort(edgs + 1 , edgs + 1 + r , cmp);
int t = 0;
for(int i = 1 ; i <= r ; i++)
{
int temp1 = edgs[i].a;
temp1 = to_find(temp1);
int temp2 = edgs[i].b;
temp2 = to_find(temp2);
int wei = edgs[i].w;
if(temp1 != temp2)
{
t += wei;
p[temp1] = temp2;
}
}
printf("%d\n",10000 * (n + m) + t);
}
return 0;
}