一道思博好题啊qwq

模型的灵活应用肥肠重要

懵逼的 题目

Orz

扯淡的 题解

我: 不会

昊哥: 你sb吗, 这题只要在每一个$A_i$和$B_i$之间连边然后找有多少个边数为奇数的联通块就好了

我: 昊哥我越来越崇拜你了


首先, 我们连边不是由球到筐连边…而是在每一个球能到达的两个筐之间连边…

感性理解一下就是你可以让球在这两个筐之间转移(联通块就意味着球可以任意钦定在哪一个筐中), 这样问题就转化成了: 在一些筐里, 分配一些球, 让这些筐中, 球为奇数的筐最少

我们发现

  • 如果要分配的球的个数为奇数的话, 你是不可能让这个联通块里所有的筐都为偶数的(从度数去考虑), 也就是奇数筐的个数要$+1$
  • 而如果要分配的球的个数为偶数的话, 是肯定可以让这个联通块里所有的筐都为偶数(也是从度数去考虑), 对答案没有贡献

然后每一个联通块中球的个数其实就是这个联通块中边的个数 (注意重边也要算上)

完了 昊哥真是太强了

沙茶的 代码

/**************************************************************
    Problem: 4874
    User: Cansult
    Language: C++
    Result: Accepted
    Time:1096 ms
    Memory:5124 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <stack>
#define MAXN (200000 + 5)
using namespace std;
struct bcj
{
    int fa, rnk;
}fa[MAXN];
int n, m, ans;
int find(int x)
{ return (fa[x].fa == x ? x : (fa[x].fa = find(fa[x].fa))); }
void uni(int x, int y)
{
    int fx = find(x), fy = find(y);
    fa[fx].fa = fy;
    if (fx != fy)
        fa[fy].rnk += fa[fx].rnk + 1;
    else
        ++fa[fy].rnk;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        fa[i].fa = i, fa[i].rnk = 0;
    for (int i = 1, srx, sry; i <= n; i++)
        scanf("%d%d", &srx, &sry), uni(srx, sry);
    for (int i = 1; i <= m; i++)
        if (find(i) == i && (fa[i].rnk & 1))
            ++ans;
    printf("%d\n", ans);
    return 0;
}

By 可能需要换一个脑子的 Cansult