CF1494D

CodyTheWolf · 2021-03-06 17:14:06 · 题解

并查集做法

思路比较简单：

• 把 a_{i,j} 相同的点对放在一颗树里，但如果对于类似在同一个 x 内，假如只存在 a_{1,2} = x ，a_{3,4} = x 这样的点对，那么应该是 (1,2) 一棵树， (3,4) 一棵树，所以应该用并查集维护联通

我们从叶子往根考虑，把点合并（一开始任何点都是独立的）：

• 首先把 a_{i,j} 相同的点对放在一个集合里

• 把这个集合从小到大枚举，设现在枚举到 p ，对于集合内的某个点对 (i,j) ，不妨设目前两点所在的树中，树根工资最大的是点 i

• • 如果 i 目前所在树的祖先，工资比 p 小，说明工资为 p 的主管还没被建出来。我们新建一个工资为 p 的节点，让 i，j的树根都指向这个节点。
• • 如果 i 目前所在树的祖先，工资等于 p，那么让 j 加入这个子树即可（树根指向 p ）

补充:

• 记得更新并查集

• 不存在 i 的工资大于 p （都还没枚举到呢）

• 创建树的过程绝对有两个下属，满足题目条件（其他的做法可能还要思考一下是否满足这个？我第一次写从树根往下放节点的做法就因为不满足这个假掉了）

CODE:

#include <iostream>
#include <vector>
using namespace std;

constexpr size_t MAXN = 1e3 + 5, MAXM = 5e3 + 5;
typedef pair<int, int> pii;
int a[MAXN][MAXN], f[MAXN], dad[MAXN];
int n, k;
vector<pii> v[MAXM];

int Find(int x) { return f[x] == x ? x : f[x] = Find(f[x]); }

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n, k = n;
    for (int i = 1; i < MAXN; i++) f[i] = i;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
            if (i < j) v[a[i][j]].push_back({ i,j });
        }
    for (int i = 0; i < MAXM; i++) {
        for (int j = v[i].size() - 1; j >= 0; j--) {
            int fx = Find(v[i][j].first), fy = Find(v[i][j].second);
            if (a[fx][fx] < a[fy][fy])
                swap(fx, fy);
            if (a[fx][fx] == i)
                dad[fy] = fx, f[fy] = fx;
            else
                k++, a[k][k] = i, dad[fx] = k, dad[fy] = k, f[fx] = k, f[fy] = k;
        }
    }
    cout << k << '\n';
    for (int i = 1; i <= k; i++) cout << a[i][i] << ' ';
    cout << '\n' << k << '\n';
    for (int i = 1; i < k; i++) cout << i << ' ' << dad[i] << '\n';
}