codeforces-731c-Socks-并查集

题目链接

题意：现在有n只袜子，每只袜子有一个颜色，总共有k种颜色，你可以改变一些袜子的颜色。现在有m天要穿袜子，给出m天穿的袜子序号，现让你最少的改变一些袜子的颜色，让m天中任意一天穿的都是颜色相同的袜子。

思路：一开始还在想是不是跟b一样贪心，后来发现就是个裸的并查集……将所有要搭配穿的袜子并在一起，然后求每个集合里的袜子总数减去最多的颜色的袜子数就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
using namespace std;
int fa[200002];
int find(int x)
{
	if(x==fa[x])return x;
	 else return fa[x]=find(fa[x]);
}
void un(int x,int y)
{
	int a=find(x);
	int b=find(y);
	if(a==b)return;
	  else
	  {
	  	fa[a]=b;
	  }
	//a=find(x);  
}
vector<int > g[200002];
 map<int,int> f;
int num[200002];
int gen[200002];
int main()
{  
	
	int i,j,k,m,n;
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&num[i]);
	    fa[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
	    un(x,y);
	}
	int cnt=0;
	for(int i=1;i<=n;i++)
	if(fa[i]!=i)
	{   //printf("ye:%d gen:%d\n",i,find(i));
		int fath=find(i);
		g[fath].push_back(i);
		//printf("size:%d\n",g[fa[i]].size());
	}
	long long ans=0;
	for(int i=1;i<=n;i++)
	if(fa[i]==i)
	{   f.clear();
		int l=g[fa[i]].size();
		int max=1;
		f[num[i]]++;
		//printf("gen：%d\n  size:%d\n",i,l);
		for(int j=0;j<l;j++)
		 {
		 	//printf("%d\n",g[i][j]);
		 	f[num[g[fa[i]][j]]]++;
		 	if(f[num[g[fa[i]][j]]]>max)max=f[num[g[fa[i]][j]]];
		 }
		ans+=l+1-max; 
	}
	printf("%lld\n",ans);
 }

哎，合肥现场赛打铁，感觉有很多想说的，下篇博客里写吧……