我设0点为超级原点，他到其他n+m个点都有一条10000的边，然后就是标准的kruskal算法


#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=50005;

int u[maxn];
int v[maxn];
int w[maxn];
int r[maxn];
int p[20005];

int n,m,re,x,y,d;

int cmp(const int i,const int j){return w[i]<w[j];}
int find(int x){
    return p[x]==x?x:p[x]=find(p[x]);
}

int kruskal()
{
    int ans=0;
    for(int i=0;i<=n+m;i++)p[i]=i;
    for(int i=0;i<re+n+m;i++)r[i]=i;
    sort(r,r+re+n+m,cmp);
    for(int i=0;i<re+n+m;i++){
       int e=r[i];
       int a=find(u[e]);
       int b=find(v[e]);
       
       if(a!=b){
          ans+=w[e];
          p[a]=b;
       }
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
       scanf("%d%d%d",&n,&m,&re);
       int k=0;
       for(;k<re;k++){
          scanf("%d%d%d",&x,&y,&d);
          u[k]=1+x;
          v[k]=n+1+y;
          w[k]=10000-d;
       }
       for(;k<re+n+m;k++){
          u[k]=0;
          v[k]=k-re+1;
          w[k]=10000;
       }
       printf("%d\n",kruskal());
       
    }
}