题解：P14766 [ICPC 2024 Seoul R] Cards Flipping

· · 题解

P14766

题目大意

有 n 张卡片，每张卡片正反面分别有两种颜色。我们可以任意翻转所有卡片。我们要经过翻转使得不同颜色的卡片数量最大。

大体思路

我们可以把每一种颜色看作一个点，把卡片看作连接正反面两种颜色的边。这样我们就得到了一个可能有重边和资环的无向图了。我们可以设有 m 条边，有 c 条顶点。

这时，我们得到的无向图有两种情况：

  1. 当 m < c 时，因为每张卡片只能展示一种颜色，即每条边只能选择一个顶点，所以我们最多只能选择 m 个顶点，即 m 个颜色。
  2. 当 m \ge c 时，因为最多只有 c 个不同的顶点，所以最多只能有 c 种颜色。

综上所述，整个图的最大不同颜色数等于所有连通分量的 min ( m , c ) 之和。

算法设计

我们要先将所有的颜色离散化，并且使用并查集维护连通分量。每一个分量都要记录顶点数 c 和边数 m。

初始时，每个颜色单独一个分量，c=1，m=0。

对于每张卡片 (u,v)：

最后遍历所有分量，累加 min(m,c) 即可。

代码

#include<bits/stdc++.h>
using namespace std;
int p[407891],r[407891];
long long v[407891],e[407891];
/*
p：并查集的父亲节点
r：并查集的秩（高度），用于优化合并操作
v：存储每个连通分量中的顶点数量
e：存储每个连通分量中的边数量
*/
int find(int x){//寻找x的根节点
    if(p[x]!=x)  p[x]=find(p[x]);
    return p[x];
}
void he(int x,int y){//将包含x和y的两个连通分量合并
    int rx=find(x),ry=find(y);
    if(rx==ry){//若x和y在一个连通分量当中，则只需将边数+1
        e[rx]++;
        return;
    }
    //否则，按秩（高度）合并
    if(r[rx]<r[ry])  swap(rx,ry);
    p[ry]=rx;
    if(r[rx]==r[ry])  r[rx]++;
    v[rx]+=v[ry];//合并定点数
    e[rx]+=e[ry]+1;//合并边数
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    int a[200091],b[200078];
    for(int i=0;i<n;i++)  cin>>a[i];
    for(int i=0;i<n;i++)  cin>>b[i];
    //离散化颜色
    unordered_map<int,int>c;
    int op=0;
    for(int i=0;i<n;i++){
        if(!c.count(a[i]))  c[a[i]]=op,op++;
        if(!c.count(b[i]))  c[b[i]]=op,op++;
    }
    //初始化并查集
    //每个节点都是自己的父节点
    //秩（高度）初始化为0
    //每个连通分量初始有1个节点，0条边
    for(int i=0;i<op;i++)  p[i]=i,r[i]=0,v[i]=1,e[i]=0;
    for(int i=0;i<n;i++){
        int u1=c[a[i]],v1=c[b[i]];
        he(u1,v1);//合并两个连通分量
    }
    long long sum=0;
    for(int i=0;i<op;i++){
        if(p[i]==i)  sum+=min(v[i],e[i]);
        //累计每个连通分量的min(顶点数,边数)
    }
    cout<<sum;//输出答案
    return 0;
}