天天看点
返回

kuangbin带你飞专题五并查集

POJ - 2236 Wireless Network

题意

两个操作：

  1. 维护电脑
  2. 查询 两台电脑是否能通信

思路

并查集

注意：

  1. 是否能通信条件 get_dist(Point a Point b) <=d && 都已维护
  2. sqrt 丢失精度问题，用 距离平方与d的平方作比较

代码 

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define sd(x) scanf("%d", &x)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
const int N = 1010;
int p[N];
PII Point[N];
bool st[N];
int n, d;

int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

bool get_dist(PII a, PII b){
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) <= d * d;
}

int main() {
    for(int i = 1; i < N; i ++)
        p[i] = i;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> d;
    for(int i = 1; i <= n; i ++) {
        cin >> Point[i].x >> Point[i].y;
    }

    string str;
    while(cin >> str) {
        int a, b;
        if(str[0] == 'O') {
            cin >> a;
            st[a] = true;
            for(int i = 1; i <= n; i ++) {
                if(get_dist(Point[a], Point[i]) && st[i]) {
                    p[find(i)] = p[a];
                }
            }
        }
        if(str[0] == 'S') {
            cin >> a >> b;
            int px = find(a), py = find(b);
            if(px != py)
                cout << "FAIL" << endl;
            else
                cout << "SUCCESS" << endl;
        }

    }
    return 0;
}

POJ1611The Suspects

思路

  1. 若一组内没人与0沾上关系，则祖先是第一个元素
  2. 若一组内有人与0沾上关系，即它的祖先是0, 则让第一个元素的祖先指向0

代码 

#include<iostream>
#include<cstring>
#include<algorithm>
#define sd(x) scanf("%d", &x)
#define rep(i, a, b) for(int i = a; i <= b; i ++)

using namespace std;

const int N = 30010;
int n, m;
int p[N];

int find(int x) {
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}

int main() {   
    while(cin >> n >> m && (n || m)) {
        rep(i, 0, n)
            p[i] = i;
        while(m --) {
            bool f = false;
            int k, sum;
            cin >> sum;
            cin >> k;
            int py = find(k);
            rep(i, 2, sum) {
                int x;
                cin >> x;
                int px = find(x);
                if(px == 0) f = true;
                p[px] = py;
            }
            if(f) p[py] = 0, p[0] = 0;
        }

        int ans = 0;
        rep(i, 0, n)
            if(find(i) == 0) ans ++;
        cout << ans << endl;
    }

    return 0;
}

HDU3038How Many Answers Are Wrong

思路

带权并查集模板提!!!

一个区间[l, r] = sum, 当成点l-1与点r 权值是sum

注意：

主要思想：并查集问题只考虑该结点与根结点的关系(矢量关系, 可+可－)

若想要树中两个点的关系也可以求出来

该题：

设定

d[x]

数组， 意义为

x

结点与

x

的祖宗的关系。

这里的关系就是距离，即

[x, p[x]]

的 区间和

若两个端点不在同一集合，即祖宗不是同一个人，则合并操作

反之，直接判断。

并操作: 

int pa = find(a), pb = find(b);
      if(pa != pb) {
          p[pa] = pb;
          d[pa] = d[b] + w - d[a];
  }
kuangbin带你飞专题五并查集

查操作 

int find(int x) {
    if(p[x] != x) {
        int root = find(p[x]);
        d[x] += d[p[x]];
        p[x] = root;
    }

    return p[x];
}

代码 

#include<iostream>
#include<cstring>
#include<algorithm>
#define sd(x) scanf("%d", &x)
#define rep(i, a, b) for(int i = a; i <= b; i ++)

using namespace std;

const int N = 200010;

int p[N];
int d[N];
int n, m;

void init() {
    rep(i, 0, N - 1){
        p[i] = i;
        d[i] = 0;
    }
}

int find(int x) {
    if(p[x] != x) {
        int root = find(p[x]);
        d[x] += d[p[x]];
        p[x] = root;
    }

    return p[x];
}

int main() {
    while(scanf("%d%d", &n, &m) != EOF) {
        init();
        int ans = 0;
        while(m --) {
            int a, b, w;
            scanf("%d%d%d", &a, &b, &w);
            a --; //[l - 1, r]
            int pa = find(a), pb = find(b);
            if(pa != pb) {
                p[pa] = pb;
                d[pa] = d[b] + w - d[a];
            }
            else {
                if(d[a] - d[b] != w) ans ++;
            }
        }

        printf("%d\n", ans);
    }

    return 0;
}

POJ1182 食物链

思路

这题具有传递性！！！！！！！！！！

什么是传递性?

A与B是好朋友，B与C是好朋友，则A和C也是好朋友，属于同一个集合。

该题

A->B, B->C,就可知道C->A

这就是传递性！！！

带权并查集

转自:Ackerman

定义两个数组

fa[ ]

和

rela[ ]

，

fa

用来判断集合关系，

rela

用来

描述其与根节点的关系

。因为关系满足

传递性

，所以可以推导出给出条件下的当前关系，在判断与之前已有关系是否矛盾。

本题的解法巧妙地利用了模运算，rela数组用0表示同类，1表示当前点能吃别人，2表示当前点被别人吃。

1.路径压缩+查找父节点

kuangbin带你飞专题五并查集
int find(int x) {
    if(x != p[x]) {
        int root = find(p[x]);
        rela[x] = (rela[x] + rela[p[x]]) % 3;
        p[x] = root;
    }
    return p[x];
}

2.合并

kuangbin带你飞专题五并查集

定义

~rela[x]

, 代表反转关系，若x吃y，则会转为y吃x

rela[x] = (3 - rela[x]) % 3

, 十分巧妙

目的算出rela[px]

void merge(int r, int x, int y) {
    int fx = find(x), fy = find(y);
    if(fx != fy) {
        p[fx] = fy;
        rela[fx] = (rela[y] + r + 3 - rela[x]) % 3;
    }
}

3.check(查找两点的关系)

kuangbin带你飞专题五并查集
if(find(x) == find(y)) {
        int relation = (rela[x] + 3 - rela[y]) % 3;
        return r == relation;
    }

完整代码 

#include<iostream>
#include<cstring>
#include<algorithm>
#define sd(x) scanf("%d", &x)
#define rep(i, a, b) for(int i = a; i <= b; i ++)

using namespace std;

const int N = 50010;
int p[N];
int rela[N];
int n, k;
int x, y, r;
int ans;

void init() {
    rep(i, 1, N - 1) {
        p[i] = i;
        rela[i] = 0;
    }
}

int find(int x) {
    if(x != p[x]) {
        int root = find(p[x]);
        rela[x] = (rela[x] + rela[p[x]]) % 3;
        p[x] = root;
    }
    return p[x];
}

void merge(int r, int x, int y) {
    int fx = find(x), fy = find(y);
    if(fx != fy) {
        p[fx] = fy;
        rela[fx] = (rela[y] + r + 3 - rela[x]) % 3;
    }
}

bool check(int r, int x, int y) {
    if(x > n || y > n)
        return false;
    if(r == 1 && x == y)
        return false;

    if(find(x) == find(y)) {
        int relation = (rela[x] + 3 - rela[y]) % 3;
        return r == relation;
    }
    else
        return true;
}
int main() {
    init();
    sd(n), sd(k);
    while(k --) {
        scanf("%d%d%d", &r, &x, &y);
        r --; //巧处, (2 --) = 1, 即吃别人, (1 --) = 0, 即同类, 和定义的rela[]匹配
        if(check(r, x, y))
            merge(r, x, y);
        else ans ++;
    }

    printf("%d\n", ans);
    return 0;
}

POJ1733 Parity game

思路

和HDU3038How Many Answers Are Wrong类似

这题也具有传递性

只不过稍微想想改成异或操作就行了

  • 两个偶区间 -> 偶区间
  • 一奇一偶 -> 奇区间
  • 两个奇区间 -> 偶区间

可用

1

表示奇数,

表示偶数, 则

1^0= 1, 0^0 = 0, 1^1= 0

还是带权并查集

考虑三个步骤，

  1. 查操作
  2. 并操作
  3. check操作

查操作

kuangbin带你飞专题五并查集

并操作

kuangbin带你飞专题五并查集

在同一集合的check操作

kuangbin带你飞专题五并查集

注意

这里n较大，而m较小，则需要用到离散化

个人认为离散化需要保序

sort + unique + lower_bound

代码 

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define sd(x) scanf("%d", &x)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#include<map>

using namespace std;

const int N = 100010;
int p[N];
int d[N];
int cnt;
int des[N * 2];
map<int, int> mp;

struct Query {
    int x, y, w;
}q[N];

void init() {
    rep(i, 1, N - 1) {
        p[i] = i;
        d[i] = 0;
    }
    cnt = 0;
    mp.clear();
}

//不保序离散化
//int Count(int x) {
//    if(!mp.count(x)) mp[x] = ++ n;
//    return mp[x];
//}

int find(int x) {
    if(p[x] != x) {
        int root = find(p[x]);
        d[x] = d[x] ^ d[p[x]];
        p[x] = root;
    }

    return p[x];
}


int main() {
    int _;
    while(cin >> _) {
        init();
        int ans = -1;
        int m;
        cin >> m;
        rep(i, 0, m - 1) {
            string str;
            int a, b, w;
            cin >> q[i].x >> q[i].y >> str;
            if(ans != -1) continue;

            des[cnt ++] = q[i].x - 1;
            des[cnt ++] = q[i].y;
            if(str[0] == 'e') q[i].w = 0;
            else q[i].w = 1;
        }

        sort(des, des + cnt);
        cnt = unique(des, des + cnt) - des;

        rep(i, 0, m - 1){
            if(ans != -1) continue;
            int x = lower_bound(des, des + cnt, q[i].x - 1) - des;
            int y = lower_bound(des, des + cnt, q[i].y) - des;
            int px = find(x), py = find(y);
            if(px != py) {
                p[px] = py;
                d[px] = q[i].w ^ d[y] ^ d[x];
            }
            else {
                int type = d[x] ^ d[y];
                if(type != q[i].w) {ans = i;}
            }
        }

        if(ans != -1) cout << ans << endl;
        else cout << m << endl;
    }

    return 0;

}

HDU1272小希的迷宫

思路

并查集模板题

注意

  1. 要判断是否连通即一棵树
  2. 输入 0 0 输出Yes

代码 

#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
#define sd(x) scanf("%d", &x)
#define rep(i, a, b) for(int i = a; i <= b; i ++)

using namespace std;

const int N = 100010;
int p[N];
set<int> S;

void init() {
    for(int i = 0; i < N; i ++)
        p[i] = i;
}

int find(int x) {
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main() {
    int x, y;
    while(~scanf("%d%d", &x, &y) && (x != -1 || y != -1)) {
        S.clear();
        bool flag = true;
        int cnt = 0;
        init();

        do {
            if(!x && !y) break;
            S.insert(x); S.insert(y);
            cnt ++;
            int px = find(x), py =  find(y);
            if(px != py) {
                p[px] = py;
            }
            else {
                flag = false;
            }
        }while(~scanf("%d%d", &x, &y));
        if(cnt == 0) {puts("Yes");continue;}
        if(flag && cnt == (int)S.size() -1) puts("Yes");
        else puts("No");
    }

    return 0;
}
kuangbin带你飞 算法
上一篇: 我在中国信网购买虚拟主机的经历
下一篇: 阿里云大陆免备案的两种方法实践

继续阅读