CodeForces - 1209D 并查集

题意：

有 n个不同的糖果，从 1到 n编号。有 k个客人。要用糖果招待客人。对于每个客人，这些糖果中恰有两个是其最爱。第 i个客人最爱的糖果编号是 xi和 y。将 k

个客人任意排列，他们按顺序去拿自己最爱的糖果。
客人要拿到至少一个最爱的糖果才满意。
求不满意的客人的最小数目。

题解：

题目让求不满意客人最小数量，那么就肯定会有这样情况发生：

3 3

1 2

1 3

刚开始1号客人喜欢1和2糖果，因为1和2号糖果都没被用过，那么我们就先把1号糖果分给1号客人，后面第二个客人喜欢1和3号糖果，因为1号糖果用过了，所以3号糖果给2号客人。后面3号客人喜欢的糖果都被用过了，这个时候就要让1号客人放弃一号糖果去用2号糖果了。

我们也就是要解决放弃某个糖果去用另一个糖果这个抉择过程

这样的话我们可以用并查集，如果一个人喜欢1和2号糖果，那么就让1和2号糖果合并到一个集合里面。

这样的话合并1号糖果和2好糖果就相当于吃了1号或2号糖果中的一个，具体吃的哪个没有确定下来。这样的话就可以解决上面的问题

过程：

如果两个糖果在同一个集合中，说明两个糖果都被吃完了，如果两个糖果不在同一个集合中，说明至少还有一个糖果可以吃，那么把他们吃掉，同时两个集合合并为一个。

代码：

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<iostream>

 4 #include<algorithm>

 5 #include<math.h>

 6 #include<vector>

 7 #include<queue>

 8 #include<stack>

 9 #include<map>

10 using namespace std;

11 typedef long long ll;

12 const int maxn=1e5+10;

13 const int INF=0x3f3f3f3f;

14 const double eps=1e-10;

15 const int mod = 1e9+7;

16 #define mt(A,B) memset(A,B,sizeof(A))

17 #define lson l,m,rt*2

18 #define rson m+1,r,rt*2+1

19 #define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

20 int v[maxn];

21 void init(int n)

22 {

23     for(int i=0; i<=n; i++)

24         v[i]=i;

25 }

26 int finds(int x)

27 {

28     if(x==v[x]) return x;

29     return v[x]=finds(v[x]);

30 }

31 bool unite(int x,int y)

32 {

33     x=finds(x);

34     y=finds(y);

35     if(x!=y)

36     {

37         v[x]=y;

38         return true;

39     }

40     return false;

41 }

42 int main()

43 {

44     SIS;

45     int n,k,x,y,ans=0;

46     cin >> n >> k;

47     init(n);

48     for(int i=0; i<k; i++)

49     {

50         cin >> x >> y;

51         if(!unite(x,y)) ans++;

52     }

53     cout << ans << endl;

54     return 0;

55 }

巴特西

CodeForces - 1209D 并查集

最新文章

热门文章