最小生成树（17）
Conscription
Time Limit:&1000MS
Memory Limit:&65536K
Total Submissions:&9673
Accepted:&3437
Description
Windy has a country, and he wants to build an army to protect his country. He has picked up&N&girls and&M&boys and wants to collect them to be his soldiers.
To collect a soldier without any privilege, he must pay 10000 RMB. There are some relationships between girls and boys and Windy can use these relationships to reduce his cost. If girl&x&and boy&y&have
a relationship&d&and one of them has been collected, Windy can collect the other one with 10000-d&RMB. Now given all the relationships between girls and boys, your assignment is to find the least amount
of money Windy has to pay. Notice that only one relationship can be used when collecting one soldier.
The first line of input is the number of test case.
The first line of each test case contains three integers,&N,&M&and&R.
Then&R&lines followed, each contains three integers&xi,&yi&and&di.
There is a blank line before each test case.
1 ≤&N,&M&≤ 10000
0 ≤&R&≤ 50,000
0 ≤&xi&&&N
0 ≤&yi&&&M
0 &&di&& 10000
For each test case output the answer in a single line.
Sample Input
Sample Output
题意：需要招募女兵N人，男兵M人。每招募一个人需要花费10000元。但是如果已与招募的人中有一些关系亲密的异性，那么可以少花一些钱。&给出R条男女间1~9999的关系值，招募某人的费用为10000-（已经被招募的人中与其关系值的最大值）。要求通过适当的顺序招募所有人，使得所需要的费用最少。
题解：x，y分别表示女兵和男兵。题目中男女有对应关系，但男兵，女兵都是从编号零开始。并不在一棵树里。我们可以把y=y+N，这样就要男生加到女生的书中成为了一棵树。我们需要找到这棵树的最大边权值（原费用(N+M)*10000-最大边权值才等于最少花费），可以把所有的边权值变为自身的负值。这样最大权森林问题就变成了最少生成树问题。
转变为最少生成树后，就变成了一道裸题。prim算法处理是在矩阵存储中容易出错，也会容易爆内存。邻接表+prim更好。&我这里用的kruskal，很方便。
代码如下：
#include&cstdio&
#include&cstring&
#include&algorithm&
#define maxn 10010
int tree[maxn*2];
struct node
int x,y,d;
}a[50010]; //注意数组啊，以R的范围开
int cmp(node a,node b)
return a.d&b.d;
int find(int x)
if(tree[x]==x)
return tree[x]=find(tree[x]);
void merge(int a,int b)
int fa=find(a);
int fb=find(b);
if(fa!=fb)
int main()
int t,n,m,R,i,j;
scanf(&%d&,&t);
while(t--)
scanf(&%d%d%d&,&n,&m,&R);
for(i=0;i&R;++i)
scanf(&%d%d%d&,&a[i].x,&a[i].y,&a[i].d);
a[i].y+=n;//将男生的树放到女生树后面
a[i].d=0-a[i].d;//将关系值变为负数就可以求最小生成树的边权值
sort(a,a+R,cmp);
for(i=0;i&n+m;++i)
tree[i]=i;
int sum=0;
for(i=0;i&R;++i)
if(find(a[i].x)!=find(a[i].y))
merge(a[i].x,a[i].y);
sum+=a[i].d;
printf(&%d\n&,(n+m)*10000+sum);//+sum是减掉关系值

&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：219290次
积分：8409
积分：8409
排名：第2191名
原创：624篇
转载：19篇
评论：48条
(1)(2)(6)(7)(14)(10)(9)(4)(13)(11)(11)(17)(22)(23)(48)(53)(51)(40)(23)(91)(57)(27)(11)(26)(9)(34)(28)}