题解 P5089 [eJOI2018]元素周期表

· · 题解

此题是一个非常常见的边点转化的一个模型。

首先注意到题目中描述的一个性质——如果任取两纵两横四个交点中有三个交点都已经出现了，那么第四个点无条件产生。

考虑将其做这样的一个转化——将每一横行和每一纵列视为一个点，而横纵的交点则为沟通这一行一列的边。那么将上面的性质用这种方式表述出来就是——如果有 4 个点已经存在三条边进行沟通，那么第四条边无条件加入。

那么这个题就被转化成为了最小生成树——因为 4 个点有三条边相连的时候第四个边不必加入，等效于加入没有权值。再往后的聚变操作如果利用到这个元素，不过是利用了这四个点的连通性，那么这条边更加可以不加入了。

注意到这里点的数目过多，而横纵行的数量级不大，因而不要暴力的跑最小生成树算法。考虑先将已经有的元素之间相互进行聚变，然后用最小生成树的终止条件来判断还需连多少条边，这样连的边数就是要买的元素个数。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
int cnt, father[400005];
int getfather(int x)
{
    return father[x] == x ? x : father[x] = getfather(father[x]);
}
vector<pair<int, int> > v;
int main()
{
    int n, m, x, y, q;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= q;i++)
    {
        scanf("%d%d", &x, &y);
        v.push_back(make_pair(x, y + n));
    }
    for (int i = 1; i <= n + m;i++)
        father[i] = i;
    long long ans = 0;
    int times = 0;
    for (int j = 0; j < v.size();j++)
        if (getfather(v[j].first) != getfather(v[j].second))
        {
            times++;
            father[getfather(v[j].first)] = getfather(v[j].second);
            if (times >= n + m - 1)//其实这句没用
                break;
        }
    //times指出了当前生成树上的边数，还需连接的边数就是要买的元素个数
    printf("%lld\n", ans + n + m - 1 - times);
    return 0;
}

同时容易发现，这种转化下任意两行或者任意两列之间不可能存在交点，因而也就没有边相连。因而这个图也是一张二部图，一张存在多个连通块的二部图。但是此处并没有过多的利用这一性质，还是基于其连通性的考量——我们需要购买的最少元素个数，一定等于沟通这些连通块所需的边数，即连通块个数 -1。