CodeForces - 1209D

题意

现在n种点心，每种点心只有一份，有k位客人，每位客人有两种想要吃的点心，你可以安排他们进场的顺序，每位客人会吃掉所有他想要吃的，并且还没被吃掉的点心。如果客人一个也没吃到，他就会不开心，问最少的不开心的人是多少？

思路

刚开始以为只会吃掉一个，直接按照第一个元素大小排序，WA了。

一直到比赛结束我都没搞清题意，赛后搜题解很懵逼，怎么和并查集扯上的关系，这不是贪心吗？

题意读错了。。。

第一个客人肯定是把两个都吃掉了，这时为了满足其他的客人，我们要选择的客人肯定是，他喜欢的其中一个被吃掉，另一个没被吃掉。

就是在已知的被吃掉的点心中，寻找没被吃掉的点心，这就是并查集的思想。

代码

//#include<bits/stdc++.h>

#include<stdio.h>

#include<algorithm>

#include<string.h>

#include<string>

#include<math.h>

#define pb push_back

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int N=1e5+10;

const int mod=1e9+7;

const int inf=0x3f3f3f3f;

const double eps=1e-14;

int fa[N];

int find(int x)

{

    if(fa[x]==x) return x;

    return fa[x]=find(fa[x]);

}

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    int ans=0;

    for(int i=1;i<=n;i++) fa[i]=i;

    for(int i=1;i<=m;i++)

    {

        int u,v;

        scanf("%d%d",&u,&v);

        int uu=find(u);

        int vv=find(v);

        if(uu==vv)

        {

            ans++;

            continue;

        }

        fa[uu]=vv;

    }

    printf("%d\n",ans);

    return 0;

}

个人博客

巴特西

CodeForces - 1209D Cow and Snacks 并查集

CodeForces - 1209D

题意

思路

代码

最新文章

热门文章