题解 CF731C 【Socks】

顾z

2018-11-05 15:24:12

Solution

> ### Description > > 有$n$只袜子,$k$种颜色,在$m$天中,问最少修改几只袜子的颜色,可以使每天要穿的袜子颜色相同。 > > ### Input > > 第一行$n,m,k$分别对应题目描述。 > > 接下来$m$行每行两个整数$l_i,r_i$表示第$i$天要穿的两只袜子的编号。 > > ### Output > > 一个整数,代表最小要修改几只袜子的颜色。 首先,对于每一天要穿的袜子,我们加入同一个并查集。(这个很明显吧) 如果有一只袜子需要被穿多次的话, 显然我们会将其染成当前联通块中包含袜子最多的一种颜色。 我们用$vector$维护每个联通块中的袜子的颜色。 再开$vis$数组维护每种袜子的出现次数。(**注意要清空**) 每次我们累加的答案就是$size-mx$ > 其中$size$为联通块大小,$mx$为颜色相同的最多的袜子的个数。 ``代码`` ```c++ #include<cstdio> #include<algorithm> #include<vector> #include<iostream> #define R register using namespace std; const int gz=200001; inline void in(R int &x) { int f=1;x=0;char s=getchar(); while(!isdigit(s)){if(s=='-')f=-1;s=getchar();} while(isdigit(s)){x=x*10+s-'0';s=getchar();} x*=f; } vector<int>v[gz]; int col[gz],f[gz],n,m,k,ans,vis[gz]; int find(R int x){return f[x]==x?x:f[x]=find(f[x]);} signed main() { in(n),in(m),in(k); for(R int i=1;i<=n;i++)in(col[i]),f[i]=i; for(R int i=1,x,y;i<=m;i++) { in(x),in(y); R int fa=find(x),fb=find(y); if(fa==fb)continue; f[fa]=fb; } for(R int i=1;i<=n;i++) { R int fa=find(i); v[fa].push_back(col[i]); } for(R int i=1;i<=n;i++) { R int tmp=v[i].size(); R int mx=0; if(tmp>1) { for(R int j=0;j<tmp;j++) { vis[v[i][j]]++; mx=max(mx,vis[v[i][j]]); } for(R int j=0;j<tmp;j++) vis[v[i][j]]--; ans+=tmp-mx; } } printf("%d",ans); } ```