题解：AT_jsc2019_qual_e Card Collector

LastKismet · 2025-11-26 14:13:22 · 题解

Sol

首先这类网格问题考虑经典地转化为二分图。具体地，左侧点代表各行，右侧点代表各列，把存在的点转化为连接其行列代表点的一条边。

考虑现在变成了一个什么问题，每个点都可以选一条临边并得到边权，每条边只能被选一次。那么选出来之后必然形如基环树森林，同时任一生成基环树森林也都可以找到相应方案。故而直接贪心地找最大权基环树森林即可，类似于 Kruskal 算法，按边权降序能加边就加边，容易反证法证明正确性。

Code

int n,r,c;
struct edge{int a,b;ll c;}es[N];

ll sum;
bool use[N],don[N];

int fa[N];
int find(int x){if(fa[x]!=x)fa[x]=find(fa[x]);return fa[x];}
void merge(int a,int b){a=find(a),b=find(b),fa[a]=b,don[b]|=don[a];}
bool same(int a,int b){return find(a)==find(b);}

inline void Main(){
    cin>>n>>r>>c;
    rep(i,1,n){
        cin>>es[i].a>>es[i].b>>es[i].c;
        es[i].b+=r;
    }
    rep(i,1,r+c)fa[i]=i;
    sort(es+1,es+1+n,[&](edge a,edge b){return a.c>b.c;});
    rep(i,1,n)if(!same(es[i].a,es[i].b)&&(!don[find(es[i].a)]||!don[find(es[i].b)])){
        use[i]=1;
        merge(es[i].a,es[i].b);
        sum+=es[i].c;
    }else if(same(es[i].a,es[i].b)&&!don[find(es[i].a)]){
        don[find(es[i].a)]=1;
        sum+=es[i].c;
    }
    put(sum);
}