HDU-6109 数据分割并查集（维护根节点）

题目链接：https://cn.vjudge.net/problem/HDU-6109

题意

给出多组等式不等式

对于每一个式子，首先判断是否不可能

如果不可能，记录本组正确式子的个数，然后进入下一组式子

思路

一开始还以为是食物链，等到写出来WA了才发现不等号不能传递（注意并查集的传递性了）

然后决定用一个set存下所有不等边，事后发现一个set难以维护和查询

最后实在不行看了题解，发现只要用一个类似线段树的PushUp来维护根节点的不等情况就好，真是一个好思路啊学习了

代码

#include <set>

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn=int(1e5);

struct Node{

    int pre, rank;

    Node(int pre=0, int rank=0):

        pre(pre), rank(rank) {}

}node[maxn+5];

set<int> diff[maxn+5];

int n, m;

int kase=0, cnt=0, ptr=0, num[maxn+5]={0};

int find(int x){

    return (node[x].pre==x)?x:(node[x].pre=find(node[x].pre));

}

void pushup(int nod, int root){

    for (set<int>::iterator it=diff[nod].begin(); it!=diff[nod].end(); it++)

        diff[root].insert(*it);

}

void join(int a, int b){

    a=find(a); b=find(b);

    if (a==b) return;

    if (node[a].rank==node[b].rank) node[a].rank++;

    if (node[a].rank>node[b].rank) {node[b].pre=a; pushup(b, a);}

    else {node[a].pre=b; pushup(a, b);}

}

inline void split(void){

    for (int i=0; i<=maxn; i++){

        diff[i].clear();

        node[i]=Node(i, 0);

    }

    num[ptr++]=cnt;

    kase++; cnt=0;

}

int main(void){

    int l, a, b, equal;

    scanf("%d", &l);

    for (int i=0; i<=maxn; i++){

        diff[i].clear();

        node[i]=Node(i, 0);

    }

    while (l--){

        cnt++;

        scanf("%d%d%d", &a, &b, &equal);

        a=find(a); b=find(b);

        if (!equal){

            if (a==b) {split(); continue;}

            diff[a].insert(b); diff[b].insert(a);

        }else{

            if (diff[a].count(b) || diff[b].count(a)) {split(); continue;}

            join(a, b);

        }

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

    for (int i=0; i<ptr; i++) printf("%d\n", num[i]);

    return 0;

}

Time	Memory	Length	Lang	Submitted
109ms	8200kB	1499	G++	2018-03-21 14:54:04

巴特西

HDU-6109 数据分割并查集（维护根节点）

题意

思路

代码

最新文章

热门文章

巴特西

HDU-6109 数据分割 并查集（维护根节点）

题意

思路

代码

最新文章

热门文章

HDU-6109 数据分割并查集（维护根节点）