AKOJ-2010-魔法石
2024-08-29 17:15:10
链接:https://oj.ahstu.cc/JudgeOnline/problem.php?id=2010
题意:
Vyoung最近收集到一大批魔法石,这些魔法石有两种特性,攻击和防守,不同特性的两个魔法石可以组合在一起形成威力巨大的武器(正确的组合),现在给你m对魔法石,检查其中有多少对与之前的组合矛盾,即组合错误的魔法石
注意组合错误即是:相同特性的魔法石是一个组合,或者自己与自己组合
思路:
带权并查集,才学的成果。
Rank数组保存i与Father[i]的关系。因为只有两种,所以用0表示同种,1表示不同种。
同理,找父亲的时候更新Rank数组。因为每个位置与父节点肯定是不同,所以初始为1。
每个点与父节点的关系,加上父节点与根节点的关系,mod2,即为每个点与根节点的关系。
而合并连个集合时。因为两个点的关系肯定为1,所以找到每个点与父节点的关系即可。
代码:
#include <iostream>
#include <memory.h>
#include <string>
#include <istream>
#include <sstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <map>
#include <queue>
#include <math.h>
using namespace std;
const int MAXN = 50000+10;
int Father[MAXN],Rank[MAXN];
int n,m; void Init()
{
for (int i = 1;i<=n;i++)
{
Father[i] = i;
Rank[i] = 0;
}
} int Get_F(int x)
{
if (Father[x] == x)
return x;
int tmp = Father[x];
Father[x] = Get_F(Father[x]);
Rank[x] = (Rank[x] + Rank[tmp])%2;//当前点与根节点的关系为当前点与父节点和父节点与根节点
return Father[x];
} void Union(int l,int r)
{
int fl = Get_F(l);
int fr = Get_F(r);
Father[fr] = fl;
Rank[fr] = (Rank[l] + 1 + Rank[r])%2;
} int main()
{
int t;
int cnt = 0,sum;
int l,r;
scanf("%d",&t);
while (t--)
{
sum = 0;
scanf("%d%d",&n,&m);
Init();
for (int i = 1;i<=m;i++)
{
scanf("%d%d",&l,&r);
int fl = Get_F(l);
int fr = Get_F(r);
if (fl == fr && Rank[l] == Rank[r])
sum++;
else
Union(l,r);
}
printf("Case #%d: %d\n",++cnt,sum);
} return 0;
}
最新文章
- 深入MySQL索引
- grep -i 不区分大小写
- C# 热敏打印机 Socket 网络链接 打印 图片
- Github的基本配置与使用
- LeetCode 笔记26 Maximum Product Subarray
- 整数划分 Integer Partition(二)
- open file 值修改
- Kill Session
- JSON 之JAVA 解析
- 【转】pybrain的使用——一个开源的python神经网络工具包
- jquery基础-包裹 替换 删除 复制
- MOSFET管应用总结
- ubuntu 修改运行级别
- 射频识别技术漫谈(27)——CPU卡概述
- 洛谷-统计数字-NOIP2007提高组复赛
- 【论文:麦克风阵列增强】An Algorithm For Linearly Constrained Adaptive Array Processing
- POJ 2566 尺取法(进阶题)
- Ext.grid.EditorGridPanel分页和查看全部
- uva1354 枚举二叉树
- AppCan移动开发技巧:3步走,获取移动APP签名信息