题意：从一个起点出发连接男孩子和女孩子，若是两者之间有连接的，则花费为10000-d，若是没有连接的则花费为10000
分析：很显然是一个最小生成树，但是我们希望的是d越大越好，因为d越大，10000-d就越小。因此我们在此处用－d来作为最小生成树边的权值，这样就能得出如何连接才能使花费最少了
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <vector> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <bitset> 10 #include <cmath> 11 #include <queue> 12 #include <stack> 13 using namespace std; 14 const int maxn=50010; 15 int n,m,r; 16 struct edge{ 17 int u,v,cost; 18 }; 19 bool cmp(const edge& e1,const edge& e2){ 20 return e1.cost<e2.cost; 21 } 22 edge es[maxn]; 23 24 //并查集部分 25 int par[maxn]; 26 int rankl[maxn]; 27 void init(int n){ 28 for(int i=0;i<=n;i++){ 29 par[i]=i; 30 rankl[i]=0; 31 } 32 } 33 int findl(int x){ 34 if(par[x]==x) 35 return x; 36 else{ 37 return par[x]=findl(par[x]); 38 } 39 } 40 void unite(int x,int y){ 41 x=findl(x); 42 y=findl(y); 43 if(x==y) return; 44 if(rankl[x]<rankl[y]){ 45 par[x]=y; 46 }else{ 47 par[y]=x; 48 if(rankl[x]==rankl[y]) rankl[x]++; 49 } 50 } 51 bool same(int x,int y){ 52 return findl(x)==findl(y); 53 } 54 55 //最小生成树 56 int kruskal(){ 57 sort(es,es+r,cmp); 58 init(n+m); 59 int res=0; 60 for(int i=0;i<r;i++){ 61 edge e=es[i]; 62 if(!same(e.u,e.v)){ 63 unite(e.u,e.v); 64 res+=e.cost; 65 } 66 } 67 return res; 68 } 69 int main() 70 { 71 int t; 72 cin>>t; 73 while(t--) 74 { 75 scanf("%d%d%d",&n,&m,&r); 76 for(int i=0;i<r;i++){ 77 int x,y,d; 78 scanf("%d%d%d",&x,&y,&d); 79 es[i].u=x,es[i].v=y+n,es[i].cost=-d; 80 } 81 printf("%d ",10000*(n+m)+kruskal()); 82 } 83 return 0; 84 }