[BZOJ4874]筐子放球 猜结论+并查集


原题链接
我们将筐看成点,球看成边,那么问题就相当于给每条边定向,最小化度数为奇数的点的数量.
结论:每个联通块内边是奇数则答案为1,否则答案为0.
显然答案不可能比这个更优,我们只需要构造出这个答案即可证明其正确性.
考虑该联通块的一棵生成树,我们可以给非树边瞎j8定向,然后自底向上用树边调整,则调整的结果肯定只跟边的奇偶性有关.
用个并查集维护即可.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 202333
using namespace std;
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
    x=0;char c=nc();
    while(!isdigit(c))c=nc();
    while(isdigit(c))x=x*10+c-'0',c=nc();
}
int n,m,ans;
int size[N],fa[N];
int find(int x)
{
    return x==fa[x]?x:(fa[x]=find(fa[x]));
}
void merge(int x,int y)
{
    x=find(x),y=find(y);
    if(x==y)size[x]++;
    else fa[x]=y,size[y]+=size[x]+1;
}
int main()
{
    read(n),read(m);
    int x,y,i;
    for(i=1;i<=m;++i)fa[i]=i;
    for(i=1;i<=n;++i)
    {
        read(x),read(y);
        merge(x,y);
    }
    for(i=1;i<=m;++i)if(i==find(i))ans+=(size[i]&1);
    cout<<ans;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注