最小生成树的模板，利用并差集 #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;#define MAXD 50000 + 100int N,M,R;int Sum;struct Line{int l;int r;int cost;}line[MA

1 首先我们应该区分开男孩和女孩，只要将男孩的编号加上女孩的个数n，这样就可以做到男孩和女孩的编号是不同的。 2 题目中说了如果两个人有关系，并且其中一个人已经被选了那么选择另外一个人的时候只要10000-d即可。所以这就涉及到了两个人的关系问题，那么自然的想到了并查集来保存关系图。所以这n+m个人最后就可以被分到s个集合里面，每一个集合里面的人都是有关系的。那么这样我们只要求出s个集合的最

题目链接： http://poj.org/problem?id=3723 题意：要征募女兵N人，男兵M人。每征一个花10000，有亲密关系则可以省相应的钱。给出R条关系以及可以省的钱。求最小花费。 输入： 2 5 5 8 4 3 6831 1 3 4583 0 0 6592 0 1 3063 3 3 4975 1 3 2049 4 2 210

题目链接：http://poj.org/problem?id=3723 题意：需要招女兵n人，男兵m人，每招一人，需要花费10000元，但是如果已经招进来的人中有一些关系亲密的人，那就可以少花一些钱，比如u和v，有关系，那么就可以少花d元，问你招到所有人，最少花多少钱 解析：其实就相当于最大生成树，然后拿10000*（n+m）减去最大生成树的值，由于这里的图可能不连通，其实应该是最大生成森林，