D. The Door Problem 带权并查集

http://codeforces.com/contest/776/problem/D

注意到每扇门都有两个东西和它连接着，那么，如果第i扇门的状态是1，也就是已经打开了，那么连接它的两个按钮的状态应该是一样的，也就是必须是同时按，或者同时不按。然后0的话就是关闭的，所以连接它的两个按钮应该是一个按，一个不按，或者相反。

所以这就是一个带权并查集（一开始没想到，以为相同的，用并查集合并就好，然后不同的，建立一个图什么的，发现有点麻烦，然后推着推着，就是带权并查集了），然后就写了很久很久，一直wa

ps，并查集初始化的那个，不能光靠n，1--n f[i] = i，不行的，因为m可能比n大。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

const int maxn = 1e5 + ;

int fa[maxn], state[maxn], siz[maxn];

int tofind(int u) {

    if (fa[u] == u) return u;

    else {

        int t = fa[u];

        fa[u] = tofind(fa[u]);

        siz[u] = (siz[t] + siz[u] + ) % ;

        return fa[u];

    }

}

bool tomerge(int x, int y, int val) {

    int tx = x, ty = y;

    x = tofind(x);

    y = tofind(y);

    if (x == y) {

        if ((siz[tx] + siz[ty] + ) %  != val) return false;

        else return true;

    } else {

        fa[y] = x;

        siz[y] = (val + siz[ty] + siz[tx]) % ;

        siz[x] = ;

        return true;

    }

}

vector<int>e[maxn];

void work() {

    int n, m;

    cin >> n >> m;

    for (int i = ; i <= n; ++i) {

        cin >> state[i];

    }

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

        fa[i] = i;

        siz[i] = ;

    }

    for (int i = ; i <= m; ++i) {

        int x;

        cin >> x;

        for (int j = ; j <= x; ++j) {

            int pos;

            cin >> pos;

            e[pos].push_back(i);

        }

    }

    for (int i = ; i <= n; ++i) {

        if (!tomerge(e[i][], e[i][], state[i])) {

            cout << "NO" << endl;

//            cout << i << endl;

            return;

        }

    }

    cout << "YES" << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}

巴特西

D. The Door Problem 带权并查集

最新文章

热门文章