翻车笔记_ bzoj4874 筐子放球 [图论, 联通块, 清奇脑回路]

一道思博好题啊qwq

模型的灵活应用肥肠重要

懵逼的 题目

Orz

扯淡的 题解

我: 不会

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

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


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

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

我们发现

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

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

完了 昊哥真是太强了

沙茶的 代码

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
/**************************************************************
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