并查集
HDU3038
2021.7.22
题意是假设有一段序列a，长度为n,接下来有m条信息 ，l r x表示a[l]+…+a[r]的这段区间之和为x,问这m条信息中哪些是错误的。比如1 100 10–1 10 1–11 100 2,很明显11 100 2是错误的，因为1 100 10 与 1 10 1可以推出11 100为9
题解
带权并查集的应用首先从题的例子来观察，如果[1,10]的和为100，[7,10]的和为28，那就能推出来[1,6]为72，注意这里不是[1,7]，因为a[7]是在[7,10]这段序列里的，现在我们建立一个带权并查集，rela[x]表示x到自己根节点的距离，1 10 100就可以表示为pre[10]=1,rela[10]=100。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 200005;
int pre[maxn];
int rela[maxn];
int Find(int x) {
if (x == pre[x])
return pre[x];
int f = Find(pre[x]);
rela[x] += rela[pre[x]];
pre[x] = f;
return pre[x];
}
void merge(int Min, int Max,int num) {
int fx = Find(Min);
int fy = Find(Max);
//合并有两种情况，可以去手推一下面两种情况得出两种情况的合并公式
//假设进来的Min为5，Max为8
//第一种情况：pre[8]=0,rela[8]=100,即有信息1 8 100,pre[5]=3,rela[5]=10,即已有信息4 5 10
//那显然应该让pre[3]=0,那rela[3]应该怎么算呢
//第二种情况：pre[8]=3,pre[5]=0，显然还是应该让pre[3]=0，但rela[3]怎么计算（建议画图理解）
if (fx != fy) {
if (fx < fy) {
pre[fy] = fx;
rela[fy] = rela[Min] + num - rela[Max];
}
else {
pre[fx] = fy;
rela[fx] = rela[Max] - num - rela[Min];
}
}
}
int n, m, ans;
int main() {
while (cin >> n >> m)
{
ans = 0;
int a, b, c;
for (int i = 0; i <= n+1; i++) {
pre[i] = i;
rela[i] = 0;
}
while (m--) {
cin >> a >> b >> c;
a--;//这里是为了前面说到的那种1 10 100和7 10 28应该推出来[1,6]为72，而不是[1,7]为28,因此假设根节点为x，子节点为y，则rela[y]表示的是(x,y]这段区间的和，即[x+1,y]的和
if (Find(a) == Find(b)) {//如果两点的祖先相同，那通过两者与根节点距离之差可以推出来两者的距离的，就能拿来与c比较
if (rela[b] - rela[a] != c) {//与已知信息矛盾，则错误信息数加一
ans++;
continue;
}
}
else {
merge(a, b, c);
}
}
cout << ans << endl;
}
return 0;
}
POJ1417 – True Liars
题意为知道好人与坏人的个数为p1，p2，并且有n条信息，每条信息格式为 a 说 b是好人或者坏人，规定好人永远说实话，坏人永远说谎话，则根据n条信息与已知的人数，能否推出哪些人是好人。
题解
==带权并查集与dp==这种n条信息的与并查集的题形式很像，首先要分析出 a b yes 的形式出现时，就代表a b是同一阵营的，a b no 则代表两者不同阵营（可以去列一下情况看看），利用带权并查集可以将人分成一颗一颗的并查集树。剩下的就是通过这些树看能不能唯一构造出符合条件的人数。
现在我们知道的只是一团一团的人，每一团里有两个阵营，但是并不知道每个团里哪个阵营是好人。
定义dp[i][j]:=前i棵树恰好凑出j个人有多少种情况，如果最后dp[NumOfTree][p1]==1,则说明有解。这道题虽然有dp但其实想到dp之后，dp的转移方程并不难，为dp[i][j]=dp[i-1][j-第i棵树中与根同一阵营的人数]+dp[i-1][j-第i棵树与根不同阵营的人数]，从转移方程中也可以看出需要记录每一棵并查集树底下两个阵营的人数，因为要输出哪些人是好人，所以每棵树还需要记录底下哪些人跟自己是同一阵营的，哪些不是。
代码如下
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int maxn = 1e3 + 5;
int pre[maxn];
vector<int> tree[maxn];//粗糙地记录根节点下有哪些节点
vector<int> same[maxn];//same[i]表树第i颗树里，与根节点相同阵营的节点编号
vector<int> differ[maxn];
int rela[maxn];//权数组，0为同一阵营，1为不同阵营
int SameNum[maxn];//SameNum[i]表示第i棵树里与根节点同一阵营的人数
int DifferNum[maxn];
int dp[maxn][maxn];
vector<int>ans;//存最后要输出哪些人
int n, p1, p2;
void init() {
for (int i = 1; i <= p1 + p2; i++) {
pre[i] = i;
same[i].clear();
differ[i].clear();
tree[i].clear();
}
memset(rela, 0, sizeof(rela));//初始情况每个人与自己同一阵营
memset(SameNum, 0, sizeof(SameNum));
memset(DifferNum, 0, sizeof(DifferNum));
memset(dp, 0, sizeof(dp));
ans.clear();
}
int Find(int x) {
if (pre[x] == x) {
return pre[x];
}
int root = Find(pre[x]);
rela[x] ^= rela[pre[x]];//带权并查集Find的套路操作，在找根的过程中要更新关系
pre[x] = root;
return pre[x];
}
void merge(int x, int y, int r) {
int fx = Find(x);
int fy = Find(y);
if (fx != fy) {
pre[fx] = fy;
rela[fx] = rela[x] ^ rela[y] ^ r;//带权并查集套路操作，使用^是应为只有0,1两种关系，其它多种关系情况要具体分析
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
while (cin >> n >> p1 >> p2) {
if (n == p1 && p1 == p2 && n == 0)
break;
init();//记得并查集每次要初始化
for (int i = 0; i < n; i++) {
int a, b;
string s;
cin >> a >> b >> s;
if (s == "yes")
merge(a, b, 0);
else
merge(a, b, 1);
}
//好人与坏人一样多，肯定判断不了
if (p1 == p2) {
cout << "no" << endl;
continue;
}
//将现在的森林第一步粗加工，使每个根节点先知道自己有哪些子孙
for (int i = 1; i <= p1 + p2; i++) {
int fa = Find(i);
tree[fa].push_back(i);
}
int cnt = 1;//用来给树编号
//第二步加工，每棵树编号，并筛出两个阵营的人数与具体哪些人
for (int i = 1; i <= p1 + p2; i++) {
if (tree[i].size()) {
for (int j = 0; j < tree[i].size(); j++) {
if (rela[tree[i][j]] == 0) {
SameNum[cnt]++;
same[cnt].push_back(tree[i][j]);
}
else {
DifferNum[cnt]++;
differ[cnt].push_back(tree[i][j]);
}
}
cnt++;
}
}
dp[0][0] = 1;//dp初始定义，注意init里面已经将dp全置为0了
//dp[i][j]:==前i棵树组出j个人的方式有多少种
for (int i = 1; i < cnt; i++) {
for (int j = 0; j <= p1; j++) {
if (j >= SameNum[i]) {
dp[i][j] += dp[i - 1][j - SameNum[i]];
}
if (j >= DifferNum[i]) {
dp[i][j] += dp[i - 1][j - DifferNum[i]];
}
}
}
if (dp[cnt - 1][p1] != 1) {//不唯一，或无解
cout << "no" << endl;
}
else {
for (int i = cnt - 1; i >= 1; i--) {
//如果最后的结果有唯一解，说明该状态下的前一个状态也一定唯一，因此从后往前推
if (p1 >= SameNum[i] && dp[i - 1][p1 - SameNum[i]] == 1) {
for (int j = 0; j < same[i].size(); j++) {
ans.push_back(same[i][j]);
}
p1 -= SameNum[i];
}
else {
for (int j = 0; j < differ[i].size(); j++) {
ans.push_back(differ[i][j]);
}
p1 -= DifferNum[i];
}
}
sort(ans.begin(), ans.end());//升序排列
for (int i = 0; i < ans.size();i++) {
cout << ans[i] << endl;
}
cout << "end" << endl;
}
}
return 0;
}
心得
看到这种类型的信息要想到是不是可能用并查集，之后分析出怎么从给出的信息来确定两个节点的关系，为了方便后面的dp，中间有很多工作都是在去优化结构来使得访问方便，也是数据结构设计为使用方便的一个体现
Connections in Galaxy War - ZOJ 3261
2021.7.20
题目大意为给定点的数量，编号0到n-1，每个点有各自的权值，再给M条信息，哪两个点直接相连。现在有Q个操作，每个操作有两种情况，一种是Query a,查询与a连通的点权值最大编号最小的点，如果最大权值比a小则输出-1，否则输出找到的编号；第二种情况是Destroy a b,表示切断a 与 b直接相连的边。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 5;
map<pair<int, int>, bool> mp;
struct node {
int a, b;
int flag;
}operation[maxn*5];
int pre[maxn];
int power[maxn];
int ans[maxn * 5];
int n, m, q;
void init() {
for (int i = 0; i < n; i++) {
pre[i] = i;
}
}
int Find(int x) {
return x == pre[x] ? x : (pre[x] = Find(pre[x]));
}
void merge(int x, int y) {
int fx = Find(x);
int fy = Find(y);
if (fx != fy) {
if (power[fx] > power[fy] || power[fx] == power[fy] && fx < fy)
pre[fy] = fx;
else
pre[fx] = fy;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int tag = 1;
while (cin >> n) {
init();
mp.clear();
if (tag == 0)
cout << endl;
else
tag = 0;
for (int i = 0; i < n; i++)
cin >> power[i];
int t;
cin >> t;
while (t--) {
int a, b;
cin >> a >> b;
if (a > b)
swap(a, b);
mp[{a, b}] = true;
}
cin >> q;
for (int i = 0; i < q; i++) {
string s;
int a, b;
cin >> s;
if (s == "query") {
cin >> a;
operation[i] = { a,0,1 };
}
else {
cin >> a >> b;
if (a > b)
swap(a, b);
operation[i] = { a,b,0 };
mp[{a, b}] = false;
}
}
for (auto& i : mp) {
if (i.second) {
merge(i.first.first, i.first.second);
}
}
int cnt = 0;
for (int i = q - 1; i >= 0; i--) {
if (operation[i].flag == 0) {
merge(operation[i].a, operation[i].b);
}
else {
int tmp = Find(operation[i].a);
if (power[tmp] > power[operation[i].a] && tmp != operation[i].a)
ans[cnt++] = tmp;
else
ans[cnt++] = -1;
}
}
for (int i = cnt - 1; i >= 0; i--) {
cout << ans[i] << endl;
}
}
return 0;
}
POJ2492 – A Bug’s Life
2021.7.20
题意是给定点的数量和关系数目，每个点都有一种性别，总共两种性别，在接下来的信息中表示两个点有互动，即两个点是异性的，判断给出的信息中是否出现了同性互动。
题解
简单带权并查集的应用 ，像这种关系只有两种的并查集可以通过异或来操作，其它情况也有相应的公式，这道题就是一行一行的扫描合并，只不过在合并过程当中如果发现已经连通要判断一下两者关系，如果两者与根节点的关系相同那两者就是同性。
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 2005;
int pre[maxn];
int rela[maxn];//关系数组，存的是节点与父亲节点的关系，而不是与根的关系，在Find那里要用到
int n, m;
int Case;
void init()
{
for (int i = 0; i <= n; i++)
pre[i] = i;
//这里初始要将rela设为0表示自己与自己是同性的
memset(rela, 0, sizeof(rela));
}
int Find(int x) {
if (x == pre[x])
return x;
int root = Find(pre[x]);
rela[x] ^= rela[pre[x]];//此时的pre[x]还是原来的父亲，由于是递归的，此刻父亲的父亲即pre[pre[x]]已经指向根节点了，而rela[pre[x]]就是此刻父亲节点与根节点的关系，由于要压缩路径需要把x的父亲指向root，因此x与root的关系可以又此刻的父亲pre[x]来搭建，就有了rela[x]^rela[pre[x]],因为这是一个只有01两种情况的并查集才用异或，其它情况就需要分析一下
pre[x] = root;//关系确定好后改变自己的父亲节点
//因此每一次调用Find都会更新出x与root的关系
return root;
}
inline void merge(int x, int y, int flag) {
int fx = Find(x);
int fy = Find(y);
if (fx != fy) {
pre[fx] = fy;
rela[fx] = rela[x] ^ rela[y] ^ flag;//套路，可以枚举一下情况看看是不是对的。其实也能理解肯定需要知道x与fx的关系和y与fy的关系，然后通过x与y的关系flag将fx与fy联系起来，只不过这里是恰好用到了异或，其它情况不一定是异或但肯定需要这三个数据
}
}
int main()
{
scanf("%d", &Case);
int id = 1;
while (Case--) {
printf("Scenario #%d:\n", id++);
scanf("%d%d", &n, &m);
init();
bool flag = true;
while (m--) {
int a, b;
scanf("%d%d", &a, &b);
if (!flag)
continue;
if (Find(a) == Find(b) && rela[a] == rela[b]) {//同祖先，与祖先的关系还相同
flag = false;
}
else {
merge(a, b, 1);
}
}
if (flag) {
printf("No suspicious bugs found!\n\n");
}
else {
printf("Suspicious bugs found!\n\n");
}
}
return 0;
}
POJ2912 – Rochambeau
2021.7.20
题意是给定人数和信息数，这些人可以被分成三组，三组的关系就是石头剪刀布的关系，相互克制，一个组的人永远出一个手势，但所有人当中有一个裁判会随便出，在接下来的信息当中能否判断谁是裁判，并输出最少判断出裁判是谁是在第几条信息之后，如果无法判断或者有矛盾的情况分别判断出来。
题解
枚举加并查集 首先可以确定的是没有裁判的话就不会有矛盾出现，因为三组人分别只会出自己那组的手势，也就是说裁判会导致矛盾的出现，那我们可以去枚举每个编号，第一层for循环用来枚举编号，并且每次都要init并查集，每条信息是以结构体存储的，第二层for枚举所有的边，用与该节点无关的边建立并查集，如果还是出现了矛盾那该节点就肯定不是裁判，记录可能是裁判的个数，最后判断是不是恰好为1,为0就是Impossible,大于1则无法判断。
最后是要判断在第几行可以得出裁判，因为要判断n-1个人都不是裁判，因此最少行应该是判断出n-1个人不是裁判里最长的那个信息，具体参见代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 505;
int pre[maxn];
int rela[maxn];
struct node {
int x, y;
char flag;//本题采用的是离线操作，需要存储每条边的信息
}r[2005];
int n, m;
int Case;
void init()
{
for (int i = 0; i <= n; i++)
pre[i] = i;
memset(rela, 0, sizeof(rela));
}
int Find(int x) {
if (x == pre[x])
return x;
int root = Find(pre[x]);
rela[x] = (rela[x] + rela[pre[x]]) % 3;//公式得出详见下图
pre[x] = root;
return root;
}
inline bool merge(int x, int y,int flag) {
int fx = Find(x);
int fy = Find(y);
if (fx != fy) {
pre[fx] = fy;
rela[fx] = (rela[y] + flag - rela[x] + 3) % 3;//公式得出详见下图
return true;
}
else {
if ((rela[x] - rela[y] + 3) % 3 != flag)
return false;
}
}
int main()
{
while (cin >> n >> m) {
for (int i = 1; i <= m; i++) {
int a, b;
char c;
cin >> r[i].x >> r[i].flag >> r[i].y;
}
int ans = 0;
int pos, lstline = 0;
for (int i = 0; i < n; i++) {
init();
bool flag = true;
for (int j = 1; j <=m; j++) {
if (r[j].x == i || r[j].y == i)
continue;
if (!merge(r[j].x, r[j].y, r[j].flag == '=' ? 0 : (r[j].flag == '<' ? 1 : 2))) {
flag = false;
lstline = max(j, lstline);//记录每次判断出来哪个编号不是裁判需要的最大边的编号
break;
}
}
if (flag) {
ans++;//记录裁判人数
pos = i;//记录裁判编号
}
}
if (ans == 0) {
printf("Impossible\n");
}
else if (ans == 1) {
printf("Player %d can be determined to be the judge after %d lines\n",pos,lstline);
}
else {
printf("Can not determine\n");
}
}
return 0;
}
POJ1733 – Parity game
2021.7.23
这道题跟how many wrong那道题很像,题意是一个01序列最多能满足到下列第几条信息
每条信息由a b s组成，表示[a,b]这段区间内1的个数为偶数或者奇数个
题解
带权并查集处理区间关系与离散化处理数据。思路也跟那道题很像，只不过那道题的关系更偏向于一种距离。容易发现如果[a,b]这段区间内的1为偶数个，那么
[1,b]与[1,a-1]含有的1的个数奇偶性是相同的，反之则相反，这就能将a,b建立起一种关系了，这个关系就是并查集需要维护的，另外的就是这道题的N开得很大，但实际数字比较少，直接开一个Pre[N]会爆空间，对数据进行一个离散化的处理即可。即假设有数据10 2 8 4 100000000，先用一个数组把这些数据存起来，之后就假设按照升序排序，那就应该是[2,4,8,10,100000000],只需要开一个pre[4]即可，利用一个中间函数Query(int)将数字映射到相应的位置即可，即假设要让100000000的根为2,那实际的操作就是pre[Query(100000000)]=pre[Query(2)],即pre[5]=pre[1]。最后有可能下面所有信息都能满足，这个地方wa了一次┑(￣Д ￣)┍
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e4 + 5;
int pre[maxn];
int pos[maxn];//离散映射数组，pos[i]表示第i大的数字
int rela[maxn];
int n, m;
int cnt = 0;
struct node {
long long a, b;
int flag;
}info[maxn];//离线操作,存储信息，一方面是离散化需要得到所有数据，一方面是就算之前能判断出结果还是需要读掉后面的数据。
int num[maxn * 2];//离散操作需要的数组，因为该数组会先存好所有数据，每条信息两个数字，开到maxn*2
//离散化函数
void decret() {
sort(num, num + m * 2);//先排序
for (int i = 0; i < m * 2; i++) {
if (!i || num[i] != num[i - 1]) {//后面这个判断是去掉那些重复的数字，防止[1,2,2,2]这种情况将2多次存到pos里面
pos[cnt++] = num[i];
}
}
}
int Query(long long x) {
return lower_bound(pos,pos+cnt, x) - pos;//x在pos中的位置就能代表x
}
int Find(int x) {
if (x == pre[x])
return pre[x];
int root = Find(pre[x]);
rela[x] ^= rela[pre[x]];
pre[x] = root;
return pre[x];
}
void merge(int x, int y,int flag) {
int fx = Find(x);
int fy = Find(y);
if (fx != fy) {
pre[fx] = fy;
rela[fx] = rela[x] ^ rela[y] ^ flag;
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m * 2; i++) {
pre[i] = i;
}
int id = 0;
char s[10];
for (int i = 0; i < m; i++) {
cin >> info[i].a >> info[i].b >> s;
if (s[0] == 'e') {
info[i].flag = 0;//如果是偶数个是不会改变之前的奇偶性的，而异或操作当中与0异或结果不变，所以用0代表是偶数个
}
else
info[i].flag = 1;
info[i].b++;//跟那道题一样，边界交界处的处理
num[id++] = info[i].a;
num[id++] = info[i].b;
}
decret();
int i;
for ( i = 0; i < m; i++) {
if (Find(Query(info[i].a)) != Find(Query(info[i].b))) {
merge(Query(info[i].a),Query(info[i].b), info[i].flag);
}
else if (rela[Query(info[i].a)] ^ rela[Query(info[i].b)] != info[i].flag){
cout << i << endl;
break;
}
}
if (i == m)//万一人家能全满足呢
cout << i << endl;
return 0;
}
POJ1984 – Navigation Nightmare
题意是有N个农场标号1到N，它们分布在一个二维平面上，两个农场之间只能由垂直或者水平的路连接.会给定m条信息 a b c s,表示农场从a往s方向走c的距离就能到达b，比如1 2 10 S表示2在1以南10的距离。需要处理输入a b index表示从前面的index条信息中能否得到a到b的曼哈顿距离,曼哈顿距离就是$|x_1-x_2|+|y_1-y_2|$.(1,2)与(5,7)的曼哈顿距离就为9
题解
多重带权并查集，如果只有一条线上是很好分析的，就是假设1到2的距离知道，2到3的距离知道那很容易推出1到3的距离，典型的一个带权并查集就够了，现在这道题是在一个二维平面上，但它的连接方式只有水平跟垂直两种，所要求的曼哈顿距离也是水平跟垂直分开求的，所以可以开两个权值数组，用来分别维护水平和竖直两个直线方向上的关系即可求解。另外需要注意一下的是这道题的index是非递减的，之前每次处理一个输入就要清空并查集再重新建立就TE了，我也是看了别人的博客才看到的，之前就一直TE ┑(￣Д ￣)┍
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int maxn = 4e4 + 5;
int n, m, k;
int pre[maxn];
int vertical[maxn];
int horisontal[maxn];
struct node {
int a, b;
int h, v;
}info[maxn];//离线操作，存储信息
void init() {
for (int i = 0; i <= n; i++) {
pre[i] = i;
vertical[i] = 0;
horisontal[i] = 0;
}
memset(info, 0, sizeof(0));//这里主要是为了把h与v置为0，但是放在静态区本来也会置为0
}
int Find(int x) {
if (x == pre[x])
return pre[x];
int root = Find(pre[x]);
//每次维护的时候两个方向的权值数组信息要同时维护
vertical[x] += vertical[pre[x]];
horisontal[x] += horisontal[pre[x]];
pre[x] = root;
return pre[x];
}
void merge(int x, int y, int ver, int hor) {
int fx = Find(x);
int fy = Find(y);
if (fx ^ fy) {
pre[fx] = fy;
//很简单的公式，画一下图就能推出来
vertical[fx] = vertical[y] + ver - vertical[x];
horisontal[fx] = horisontal[y] + hor - horisontal[x];
}
}
int main()
{
cin >> n >> m;
init();
char s[10];
int tmp;
for (int i = 1; i <= m; i++)
{
cin >> info[i].a >> info[i].b;
cin >> tmp >> s;
if (s[0] == 'N') {
info[i].h = tmp;
}
else if (s[0] == 'S') {
info[i].h = -tmp;//规定好方向
}
else if (s[0] == 'E') {
info[i].v = tmp;
}
else {
info[i].v = -tmp;
}
}
cin >> k;
int now = 1;
while (k--) {
int a, b, c;
cin >> a >> b >> c;
for (; now <= c; now++) {//由于index非递减才有这个for循环
merge(info[now].a, info[now].b, info[now].v, info[now].h);
}
if (Find(a) != Find(b)) {
cout << "-1" << endl;
}
else {
cout << abs(vertical[a] - vertical[b]) + abs(horisontal[a] - horisontal[b]) << endl;
}
}
return 0;
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 2128099421@qq.com
