题目链接
Card Collector - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路
将每一行、每一列转化为点，第i行第j列的卡牌转化为i->j+m（m为行数）的有向边。
总共会抽取m+n（m为行数，n为列数）张牌，每个点的出度为1。结果图为基环森林；
那么题目就转化为求最大基环森林。
代码
1 #include<bits/stdc++.h>
2 using namespace std;
3
4 const int N=100005;
5
6 struct EDGE{
7 int x,y,w;
8 }edge[N];
9 bool cmp(EDGE a, EDGE b){
10 return a.w>b.w;
11 }
12
13 bool f[N*2];//每个联通块是否有环
14 int fa[N*2];
15 int find(int x){
16 if(fa[x]==x) return x;
17 return fa[x]=find(fa[x]);
18 }
19
20 int main(){
21 int e,m,n;
22 scanf("%d %d %d", &e, &m, &n);
23 for(int i=1;i<=e;i++){
24 scanf("%d %d %d", &edge[i].x, &edge[i].y, &edge[i].w);
25 edge[i].y+=m;
26 }
27 sort(edge+1,edge+e+1,cmp);
28 for(int i=1;i<=n+m;i++) fa[i]=i;
29 long long ans=0;//需要开long long
30 for(int i=1;i<=e;i++){
31 int x=edge[i].x,y=edge[i].y,w=edge[i].w;
32 int p=find(x),q=find(y);
33 if(p==q&&!f[p]) ans+=w,f[p]=1;
34 else if(p!=q&&!(f[p]&f[q])){//不在同一连通块&&两个连通块不是都有环
35 f[q]=f[q]|f[p];//更新是否有环
36 fa[p]=q;
37 ans+=w;
38 }
39 }
40 cout<<ans;
41 return 0;
42 }