洛谷AT_jsc2019_qual_e Card Collector 题解

题目链接

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 }