打击犯罪(black)

2024-05-16 10:20

文章标签 black 打击犯罪

本文主要是介绍打击犯罪(black)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

线上OJ：

一本通：1386：打击犯罪(black)

核心思想：

1、如果按照题意，从1~k的顺序进行删除（枚举），则每次枚举完都要重置并查集，比较麻烦。

2、考虑逆向思维， 不从1 ~ k 顺序删除，而是从 n ~ k 逆序往图中添加。

a. 如果添加到 k 时，最大集合的元素数量不超过 n/2 ，则说明k还可以继续减小

b. 如果添加到 k 时，最大集合的元素数量开始超过 n/2，则这个 k 点不能加入，也就是说：这个k点必须删除

备注：这个点k就是题目要求的k的最小值。因为把k删除后，最大集合的元素数量不超过 n/2；如果把比k大的元素删除，更加不会超过n/2。

3、初始化每个节点时，除了初始化p[i]=i，还要初始化cnt[i] = 1，表示 i 所在集合的元素的数量仅为自己。

4、由于是逆序把 k 添加进图（图中只有比k大的点），所以在分析k 的边时，只考虑已经在图中的点（即e[k][j] > k的点）

5、如果点k和点e[k][j] 尚不在一个集合中，则合并根节点，并更新根节点所在集合的元素数量（此处不需要更新每个点的cnt，只需更新根节点的cnt，因为后续的累加也只拿根节点来累加）

题解代码：

#include <bits/stdc++.h>
using namespace std;const int N = 1005;int n, p[N], cnt[N]; // p[i]表示 i 的根节点；cnt[i] 表示 i 所在集合的元素的数量
int e[N][N]; // e[i][0] 存储 i 有几条边；e[i][1] 存储 i 的第 1 条边连接的点... e[i][j] 存储 i 的第 j 条边连接的点int find(int x)  // 找根节点
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}int main()
{scanf("%d", &n);for(int i = 1; i <= n; i++){p[i] = i;  // 初始化每个元素的根节点为自己（即每个元素都是独立的）cnt[i] = 1;// 初始化时，每个元素所在的集合都只有自己，所以 cnt 均为 1}// 读入数据，建立边for(int i = 1; i <= n; i++){scanf("%d", &e[i][0]); // 先存入i号节点边的数量for(int j = 1; j <= e[i][0]; j++)scanf("%d", &e[i][j]); // 再存入 i 的第 j 条边连接的点}// 核心代码：逆向处理，每次把 k 加入图中，并看新加入点导致的集合数量是否超过n/2for(int k = n; k >= 1; k --)  {for(int j = 1; j <= e[k][0]; j++)  // 分析与k相连的每一个点{if(e[k][j] > k)  // 由于是逆向把点加入图中。所以只有编号 >k 的点当前才在图中，才需要合并{int x = find(k), y = find(e[k][j]);if(x != y) // 如果点k和点e[k][j] 尚不在一个集合中{p[y] = x;  // 则合并根节点cnt[x] += cnt[y]; // 更新根节点所在集合的元素数量（此处不需要更新每个点的cnt,只需更新根节点的cnt，因为后续的累加也只拿根节点来累加）if(cnt[x] * 2 > n){printf("%d\n", k);return 0;}}}}}return 0;
}