Menu
Article ACM

HDU 5486 Difference of Clustering

NodeKey

NodeKey

• 2 min read

这种题目就是专门针对我的……
思路简单，所需注意细节多。

题意：
给你每个元素所在集合，问你有多少个，分割，聚集，映射关系。

思路：
首先很直接的思路就是把每个集合的元素都表示出来，进一步的说hash一下，但集合元素多，集合数量也不少，hash有点困难。
考虑将不同集合的所有相同元素用一个元素表示 (这个只要排序去重即可)
那么对于两个存在这个相同元素的集合 A, B，有如下四种讨论情况：

  1. A有若干个元素而B没有 —-> 聚集
  2. B有若干个元素而A没有 —-> 分割
  3. A,B各自存在不同元素是另一个集合不存在的 —–> 不参与讨论
  4. 不存在相异的元素 —-> 映射

顺便提示一下集合编号在 int 范围内， 要离散化……

淦

AC Code

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
const int maxn = 2e6 + 6;

int head[maxn];
struct node {
    int to, next;
} edges[maxn];

int idx;
int deg[maxn];
pii nodes[maxn];
map<int, int> uid, vid;

bool cmp(const pii& a, const pii& b)
{
    return a.first == b.first ? a.second < b.second : a.first < b.first;
}

void addEdge(int u, int v)
{
    edges[idx] = (node){ v, head[u] };
    head[u] = idx++;
}

void init()
{
    memset(head, -1, sizeof head);
    memset(deg, 0, sizeof deg);
    uid.clear(), vid.clear();
    idx = 0;
}

int main()
{
    int T, n, cas = 0, u, v;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        init();
        int ui = 0, vi = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &u, &v);
            if (uid.count(u) == 0)
                uid[u] = ++ui;
            if (vid.count(v) == 0)
                vid[v] = ++vi;
            u = uid[u], v = vid[v];
            nodes[i] = make_pair(u, v);
        }
        sort(nodes, nodes + n, cmp);
        for (int i = 0; i < n; i++)
            if (i == n - 1 || nodes[i].first != nodes[i + 1].first || nodes[i].second != nodes[i + 1].second) {
                int old = nodes[i].first, now = nodes[i].second + n;
                addEdge(old, now);
                addEdge(now, old);
                deg[old]++, deg[now]++;
            }
        int ans1 = 0, ans2 = 0, ans3 = 0;
        for (int u = 1; u <= ui; u++) {
            if (deg[u] > 1) {
                bool flag = true;
                for (int id = head[u]; ~id; id = edges[id].next) {
                    if (deg[edges[id].to] != 1) {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    ans1++;
            } else if (deg[u] == 1) {
                if (deg[edges[head[u]].to] == 1)
                    ans3++;
            }
        }
        for (int u = 1; u <= vi; u++) {
            if (deg[u + n] > 1) {
                bool flag = true;
                for (int id = head[u + n]; ~id; id = edges[id].next) {
                    if (deg[edges[id].to] != 1) {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    ans2++;
            }
        }
        printf("Case #%d: %d %d %d\n", ++cas, ans1, ans2, ans3);
    }
    return 0;
}
Share