最大生成仙人掌

题目描述

给定带权完全图 $G = (V, E)$，其中 $V = \{1, 2, \ldots, n\}$，边 $(i, j)$ 的权值为 $|i - j|$。求 $G$ 的最大生成仙人掌的边权和，并给出一组构造。

仙人掌图定义：任意两条边至多有一个公共顶点的连通图（每条边至多属于一个简单环）。

输入格式

一行包含一个正整数 $n$，表示图的点数。

输出格式

第一行：最大边权和
第二行：边数 $k$
接下来 $k$ 行：每行两个整数 $u, v$ 表示一条边

算法思路

关键数学观察

1. 理论最大值：通过组合数学分析，最大边权和为：

   $$w = \left\lfloor \frac{8(n-1)^2 + 4}{9} \right\rfloor $$

2. 最优结构：当 $n \to \infty$ 时，边权和趋近于 $\frac{8}{9}n^2$

3. 构造策略：使用 3-环（三角形）和 4-环（四边形）的组合来逼近理论最大值

核心构造方法

状态划分

将点集划分为几个部分：

• L：左端点集（连接点 $n$）
• R：右端点集（连接点 $1$）
• 中间部分：通过环结构连接

根据 $n \bmod 9$ 的余数调整各部分大小：

b = n / 9;
switch (n % 9) {
    case 0:  L = 2*b, l = b, m = 3*b-1, r = b, R = 2*b; break;
    case 1:  
    case 2:  L = 2*b+1, l = b, m = 3*b, r = b, R = 2*b; break;
    case 3:  
    case 4:  L = 2*b+1, l = b, m = 3*b+1, r = b, R = 2*b+1; break;
    case 5:  
    case 6:  L = 2*b+2, l = b, m = 3*b+2, r = b, R = 2*b+1; break;
    case 7:  L = 2*b+2, l = b, m = 3*b+3, r = b, R = 2*b+2; break;
    case 8:  L = 2*b+2, l = b+1, m = 3*b+2, r = b+1, R = 2*b+2; break;
}

环构造操作

3-环构造（三角形）：

void cyc3(const pair<int,int> &u, int mid) {
    link(u.first, u.second);  // 基础边
    link(u.first, mid);       // 连接中点
    link(u.second, mid);      // 完成三角形
}

4-环构造（四边形）：

void cyc4(const pair<int,int> &u, int ml, int mr) {
    link(u.first, u.second);  // 基础边
    link(ml, mr);             // 对边
    link(u.first, mr);        // 交叉连接
    link(u.second, ml);       // 完成四边形
}

算法流程

1. 初始化阶段

   • 计算理论最大边权和
   • 处理边界情况 ($n < 3$)

2. 核心构造阶段

   // 步骤1: 建立基础环结构
   cyc[C++] = {1, n};  // 最大权值边
   
   // 步骤2: 连接左端点集到点n
   for (i = 2; i <= L; i++) 
       cyc[C++] = {i, n};
   
   // 步骤3: 连接右端点集到点1  
   for (i = n-R+1; i < n; i++)
       cyc[C++] = {1, i};
   
   // 步骤4: 构造4-环
   i = L+1, j = n-R;
   for (k = l; k; k--, i++, j--)
       cyc4(cyc[c++], i, j);
   
   // 步骤5: 构造3-环
   for (k = m; k; k--, i++)
       cyc3(cyc[c++], i);
   
   // 步骤6: 连接剩余点到点1
   for (; i <= j; i++)
       link(1, i);
   

3. 输出验证阶段

   • 排序输出所有边
   • 验证边权和等于理论值

完整代码框架

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int n, cycle_count;
pii cycles[500005];
vector<pii> edges;
long long total_weight;

inline void add_edge(int x, int y) {
    edges.emplace_back(min(x, y), max(x, y));
    total_weight += abs(x - y);
}

inline void build_triangle(const pii &base, int vertex) {
    add_edge(base.first, base.second);
    add_edge(base.first, vertex);
    add_edge(base.second, vertex);
}

inline void build_quadrilateral(const pii &base, int left_v, int right_v) {
    add_edge(base.first, base.second);
    add_edge(left_v, right_v);
    add_edge(base.first, right_v);
    add_edge(base.second, left_v);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    
    // 计算理论最大边权和
    long long max_weight = (8LL * (n - 1) * (n - 1) + 4) / 9;
    cout << max_weight << '\n';
    
    if (n < 2) {
        cout << "0\n";
        return 0;
    }
    if (n == 2) {
        cout << "1\n1 2\n";
        return 0;
    }
    
    // 根据n mod 9确定划分参数
    int base = n / 9;
    int L, left_quads, middle_tris, right_quads, R;
    
    switch (n % 9) {
        // 各种情况的参数设置...
    }
    
    // 执行构造算法
    // [具体构造步骤...]
    
    // 输出结果
    sort(edges.begin(), edges.end());
    cout << edges.size() << '\n';
    for (auto &edge : edges) {
        cout << edge.first << ' ' << edge.second << '\n';
    }
    
    return 0;
}

算法正确性

构造验证

1. 仙人掌性质：每个环都是独立的3-环或4-环，满足仙人掌图定义
2. 连通性：通过点1和点n的连接保证图连通
3. 边权最大化：优先使用跨度大的边（如1-n），充分利用|i-j|权重特性

数学保证

• 参数划分确保总边数接近理论最大值
• 模9分类讨论覆盖所有情况
• 最终边权和验证确保计算正确

复杂度分析

• 时间复杂度：$O(n)$，线性构造
• 空间复杂度：$O(n)$，存储边集
• 最优性：逼近理论最大值 $\frac{8}{9}n^2$

样例验证

对于 $n = 4$：

• 理论值：$\frac{8 \times 3^2 + 4}{9} = 8$
• 构造：四边形 {1,3,2,4}，边权和 = 2+3+1+2 = 8

该算法通过精妙的数学分析和组合构造，高效解决了最大生成仙人掌问题。