首页 > 代码库 > [BZOJ 1854] [Scoi2010] 游戏
[BZOJ 1854] [Scoi2010] 游戏
题目链接：BZOJ - 1854
题目分析
这道题目有一种巧妙的使用并查集的做法 : 我们把每个数看作一个点，那么开始时每个点单独作为一个集合。对于每个卡片 (a,b) ，就是 a 与 b 之间连了一条边。（这里不是卡片是武器...不过都一样）
那么在一个联通分量中，如果这个联通分量点数为 n ，边不存在环，那么可以满足任选 n-1 个点（显然选最小的 n-1 个最优，即不选最大的那个）。如果存在环，那么所有 n 个点都可满足。
对于每个 (a,b) ，我们先判断 a 与 b 是否已经联通，如果是，那么这就出现了环，a与b所在的集合的最大元素就也可以取了。
如果不联通，就把较小的一个集合的最大元素设为可以取，再将两个集合联通。这里一定要注意的是，如果较小的集合的最大元素已经可以取了，那么说明小集合含有环，那么联通后的整个集合也存在环，所以就把较大集合的最大元素设为可以取，这个十分易忽视，但是数据弱所以也不会WA... 注意：我们要求每个集合的代表元素为最大的元素，所以合并的时候注意顺序，不能用什么按秩合并之类的优化。
最后从 1 开始一直向后一个个看能否取，如果不能取了就停止，输出答案。
代码
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int MaxN = 1000000 + 5;int n, a, b;int f[MaxN];bool Can[MaxN];int Find(int x) { int i, j, k; j = x; while (j != f[j]) j = f[j]; i = x; while (i != j) { k = i; i = f[i]; f[k] = j; } return j;}void Esun(int x, int y) { if (Can[x]) Can[y] = true; else Can[x] = true; f[x] = y;}int main(){ scanf("%d", &n); for (int i = 1; i <= 10005; ++i) f[i] = i; memset(Can, 0, sizeof(Can)); for (int i = 1; i <= n; ++i) { scanf("%d%d", &a, &b); int Fa = Find(a), Fb = Find(b); if (Fa > Fb) swap(Fa, Fb); if (Fa == Fb) Can[Fa] = true; else Esun(Fa, Fb); } int Ans = 0; while (Can[Ans + 1]) ++Ans; printf("%d\n", Ans); return 0;}
[BZOJ 1854] [Scoi2010] 游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。