POJ 3723 Conscription MST

题目大意：

需要征募女兵N人，男兵M人，没征募一个人需要花费10000美元，但是如果已经征募的人中有一些关系亲密的人，那么可以少花一些钱，给出若干男女之间的1~9999之间的亲密度关系，征募某个人的费用是10000-（已经征募的人中和自己的亲密度的最大值），要求通过适当的征募顺序使得征募所有人的花费最小。

思路：

好几天没刷题，来水一发

征募了某个人a时，如果使用了a和b之间的关系，那么就连一条从a到b的边。那么根据贪心算法，每次选择最大的边，那么最后减去的花费就最多，也就是求最大生成树。

#include
  
   
#include
   
     #include
    
      using namespace std; const int cost=10000; const int MAXN=20000+10; const int MAXM=50000+10; int n,m,r,fa[MAXN]; struct edge { int from,to,val; }e[MAXM]; bool operator <(const edge& a,const edge &b) { return a.val>b.val; } int find(int cur) { return cur==fa[cur]  cur:fa[cur]=find(fa[cur]); } int main() { int T; scanf(%d,&T); while(T--) { scanf(%d%d%d,&n,&m,&r); for(int i=0;i