「KTSC 2024 R2」岛屿 题解

问题分析

我们需要在一个正 $N$ 边形的三角剖分（由 $N-3$ 条对角线构成）基础上，通过添加新顶点来构造两棵边不相交的生成树。

关键观察：初始的三角剖分图是一个平面图，我们可以利用其平面性质来构造两棵互补的生成树。

算法思路：对偶图构造

核心思想

将原图的三角剖分看作一个平面图，其对偶图恰好是一棵树。我们可以利用这个性质来分离出两棵边不相交的生成树。

1. 数据结构初始化

const int NN = 2e5 + 9;
int n;
int p[NN];
vector<pair<int, int>> E;
int fa[NN];                    // 并查集
vector<int> e[NN];             // 邻接表

inline int gfa(int i) {
    return i == fa[i] ? i : fa[i] = gfa(fa[i]);
}

2. 边排序与图构建

void construct_two_trees(int N, std::vector<int> U, std::vector<int> V) {
    n = N;
    
    // 对边进行标准化排序
    for (int i = 0; i < n - 3; i ++) {
        E.emplace_back(min(U[i], V[i]), max(U[i], V[i]));
    }
    sort(E.begin(), E.end());
    for (int i = 0; i < n - 3; i ++)
        U[i] = E[i].first, V[i] = E[i].second;

目的：确保每条边都以 (较小点, 较大点) 的形式存储，便于后续处理。

3. 构建第一棵树（最大生成树）

vector<array<int, 2>> t0, t1;  // t0: 第一棵树, t1: 第二棵树的候选边

// 初始化并查集
for (int i = 0; i < n; i ++)
    fa[i] = i;

// 使用Kruskal算法构建第一棵树（内陆道路部分）
for (int i = 0; i < n - 3; i ++) {
    int x = gfa(U[i]), y = gfa(V[i]);
    if (x != y) {
        fa[x] = y;
        e[U[i]].push_back(V[i]);  // 构建邻接表
        e[V[i]].push_back(U[i]);
        t0.push_back(array<int, 2>({U[i], V[i]}));  // 加入第一棵树
    } else {
        t1.push_back(array<int, 2>({U[i], V[i]}));  // 剩余边加入第二棵树候选
    }
}

4. 添加海滨道路完成第一棵树

// 添加海滨道路完成连通性
for (int i = 0; i < n - 1; i ++)
    if (gfa(i) != gfa(i + 1)) {
        fa[gfa(i)] = gfa(i + 1);
        t0.push_back(array<int, 2>({i, i + 1}));    // 加入第一棵树
        e[i].push_back(i + 1);
        e[i + 1].push_back(i);
    } else {
        t1.push_back(array<int, 2>({i, i + 1}));    // 剩余边加入第二棵树候选
    }

// 添加最后一条海滨道路（连接n-1和0）
t1.push_back(array<int, 2>({0, n - 1}));

此时状态：

• t0 包含了原图的一棵生成树
• t1 包含了剩余的边（将用于构建第二棵树）

5. 寻找关键三角形添加新顶点

int x = -1, y = -1, z = -1;

// 寻找一个度数为3的顶点及其相邻边构成的三角形
for (int i = 0; i < n; i ++) {
    if (e[i].empty()) continue;
    sort(e[i].begin(), e[i].end());
    
    // 情况1：顶点连接0和n-1（边界情况）
    if (e[i].front() == 0 && e[i].back() == n - 1) {
        x = i, y = 0, z = n - 1;
        break;
    }
    
    // 情况2：顶点连接两个连续编号的顶点
    for (int j = 0; j < (int)e[i].size() - 1; j ++)
        if (e[i][j] + 1 == e[i][j + 1]) {
            x = i, y = e[i][j], z = e[i][j] + 1;
            break;
        }
    
    if (x != -1) break;
}

assert(x != -1);  // 确保找到了合适的三角形

算法原理：在平面三角剖分中，总能找到一个度数为3的顶点，其与邻居构成一个三角形。

6. 添加新顶点并完成第二棵树

// 在三角形(x,y,z)的中心添加新顶点
int w = add_vertex(x, y, z);

// 更新两棵树
t0.push_back(array<int, 2>({y, w}));  // 第一棵树添加新边
t1.push_back(array<int, 2>({x, w}));  // 第二棵树添加新边
t1.push_back(array<int, 2>({z, w}));

// 报告结果
report(t0);
report(t1);

最终构造：

• 第一棵树 t0：包含原生成树 + 新边 (y, w)
• 第二棵树 t1：包含剩余边 + 新边 (x, w) 和 (z, w)

复杂度分析

• 边排序：$O(N \log N)$
• 并查集操作：$O(N \alpha(N))$
• 三角形查找：$O(N)$
• 总复杂度：$O(N \log N)$，满足 $N \leq 2 \times 10^5$ 的要求

正确性证明

关键性质

$1.$ 平面性：三角剖分图是平面图，其对偶图是树

$2.$ 度数性质：在三角剖分中，存在度数为3的顶点

$3.$ 连通性：通过添加新顶点，可以保证两棵树都连通所有顶点

边不相交性

• 原边被恰当地分配到两棵树中
• 新添加的边 (y,w)、(x,w)、(z,w) 分别属于不同的树
• 所有边都不重复

算法优势

$1.$ 高效性：$O(N \log N)$ 时间复杂度

$2.$ 最优性：只添加1个新顶点，达到理论下界

$3.$ 通用性：适用于任意规模的三角剖分图

$4.$ 简洁性：算法逻辑清晰，易于实现

该解法通过平面图性质和巧妙的顶点添加策略，高效解决了三角剖分图上的双生成树构造问题。