魔术球问题

题目解析

这是一道经典的网络流（Network Flow）题目，具体来说，它是有向无环图（DAG）的最小路径覆盖问题。

问题转化

我们要把球放到 $n$ 根柱子上，实际上是要把这些球（数字）串成 $n$ 条“链”。

如果不考虑柱子数量限制，每个球都可以单独占一根柱子。
如果我们把球 $i$ 和球 $j$ 放在同一根柱子上（ $i$ 在下， $j$ 在上），就相当于把 $i$ 和 $j$ 连起来。
我们的目标是：在连线数量尽可能多的情况下（也就是合并的球越多，需要的柱子越少），看最多能容纳多少个球，使得需要的柱子数 $\le n$ 。

观察本题，对于一个进来的编号的球，他有两种情况，

放在某个和他组成平方数的球的后面

独立门户

枚举球数，球数每增加1就建立新加入的球的关系，并且重复地跑最大流。柱子数对于球数存在一种单调递增的相关关系，我们这样可以求出某一柱子数下最多能放置的球数，因为当新加入的球能够加入柱子时，重复跑最大流是能得到新流（即：该球可与其他球构成新的相邻关系）的，只要一直能得到新流，就说明柱子上还可以再加，当有一次得不到新流，就说明柱子满了，新加入的球并没能加入到任何一个柱子上。此时我们就加柱子。直到柱子加到超过n，此时的球数-1就是最大球数（因为此时实际上柱子加到超过n了）。

图论建模

我们可以将每个球看作图中的一个节点。

连边规则：如果 $i < j$ 且 $i + j$ 是完全平方数，则从 $i$ 向 $j$ 连一条有向边 ( $i \to j$ )。
物理意义：这条边代表球 $j$ 可以放在球 $i$ 的上面。

最小路径覆盖

在这个 DAG 中，我们需要用最少的路径（柱子）覆盖所有的点（球）。根据图论定理：

\text{最小路径覆盖数} = \text{节点总数} - \text{最大匹配数}

通过二分图匹配（或最大流）求解：

我们可以依次枚举球的数量 $k = 1, 2, 3, \dots$ 。
每增加一个球 $k$ ，就将其作为一个新节点加入图，并尝试寻找增广路（增加匹配数）。
计算当前需要的柱子数： $P = k - \text{current\_max\_match}$ 。
如果 $P > n$ ，说明 $n$ 根柱子已经放不下 $k$ 个球了，那么答案就是 $k-1$ 。

匈牙利算法

我们使用**匈牙利算法（Hungarian Algorithm）或网络流（Dinic）**来通过最大匹配解决此问题。鉴于数据规模 $N \le 55$ ，球的总数大概在 1600 左右，匈牙利算法编写简单且效率足够。

初始化：当前球编号 now = 0，匹配数 ans = 0。
循环：
- now++ （尝试加入下一个球）。
- 构建边：遍历所有 $i < now$ ，如果 $i + now$ 是完全平方数，则建立二分图的边（ $i$ 属于左部， $now$ 属于右部）。
- 增广：尝试为 $now$ 寻找匹配。如果找到了匹配，说明我们可以把 $now$ 接在某个球后面，匹配数 ans++。
- 检查：计算当前柱子数 pillars = now - ans。
- 如果 pillars > n，循环结束，最大球数为 now - 1。
输出方案：
- 利用匹配数组（记录谁连着谁），找出所有“路径的起点”（没有球放在它下面的球）。
- 沿着匹配关系打印整条路径。

代码

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-16 14:46:44
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

// 预估最大球数，N=55时球数大约在1600左右，2005足够
const int MAXN = 3005; 
int n; // 柱子数量

// ------------------- 模板开始 (微调以适应本题逻辑) -------------------
vector<int> adj[MAXN]; // 邻接表：adj[u] 存的是左边点 u 能连到的右边点 v (u < v)
int match[MAXN];       // match[v] = u：表示【右边】的点 v (较大数) 匹配了【左边】的点 u (较小数)
int match_left[MAXN];  // 辅助数组：match_left[u] = v，表示左边点 u 匹配了 v。用于快速找未匹配点和输出
bool vis[MAXN];        // 访问标记

// 添加边：u (小) -> v (大)
void add_edge(int u, int v) {
    adj[u].push_back(v);
}

// DFS 寻找增广路
// u 是左边的点
bool dfs(int u) {
    for (int v : adj[u]) {
        if (vis[v]) continue; 
        vis[v] = true;        

        // 如果 v 没有匹配，或者 v 的匹配对象能找到下家
        if (match[v] == 0 || dfs(match[v])) {
            match[v] = u; // 更新匹配关系：v 的上面是 u
            return true;
        }
    }
    return false; 
}
// ------------------- 模板结束 -------------------

// 判断是否为完全平方数
bool is_sq(int x) {
    int r = sqrt(x);
    return r * r == x;
}

// 记录路径的后继，用于输出
int nxt[MAXN]; 
// 标记是否有前驱，用于找柱子的底座
bool has_prev[MAXN];

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    
    cin >> n;

    int ball = 0;      // 当前球的编号
    int max_match = 0; // 当前的最大匹配数
    
    // 增量构建图
    while (true) {
        ball++; // 尝试放入下一个球
        
        // 1. 建边：看旧球 i 能否放在新球 ball 下面 (i -> ball)
        for (int i = 1; i < ball; i++) {
            if (is_sq(i + ball)) {
                add_edge(i, ball);
            }
        }
        
        // 2. 尝试增广
        // 我们只需要看增加这个球后，能否让匹配数+1
        // 增广路必须从一个【当前没有匹配的左部点】开始
        // 为了方便，我们需要维护 match_left 或者每次重算
        
        // 重建 match_left 映射以便快速查找未匹配点
        for(int i=0;i<=ball;i++) match_left[i] = 0;
        for(int v=1; v<=ball; v++) {
            if (match[v] != 0) match_left[match[v]] = v;
        }

        bool found = false;
        // 遍历所有可能的左部点 i
        for (int i = 1; i < ball; i++) {
            // 只有未匹配的点才可能作为增广路的起点
            if (match_left[i] == 0) {
                // 清空访问标记，开始新的一轮寻找
                for(int k=0; k<=ball; k++) vis[k] = 0; 
                
                if (dfs(i)) {
                    max_match++; // 找到一条增广路，匹配数+1
                    found = true;
                    break; // 对于每增加一个球，最多只能增加1个匹配，找到即停
                }
            }
        }
        
        // 3. 检查柱子数量
        // 最小路径覆盖 = 节点总数 - 最大匹配数
        int pillars = ball - max_match;
        
        if (pillars > n) {
            ball--; // 这个球放不下了，回退
            break;
        }
    }
    
    // 输出总球数
    cout << ball << "\n";
    
    // 重构路径用于输出
    // match[v] = u 表示 u -> v
    memset(nxt, 0, sizeof(nxt));
    memset(has_prev, 0, sizeof(has_prev));
    
    for (int v = 1; v <= ball; v++) {
        if (match[v] != 0) {
            int u = match[v];
            nxt[u] = v;
            has_prev[v] = true;
        }
    }
    
    // 打印每根柱子
    for (int i = 1; i <= ball; i++) {
        // 如果 i 没有前驱，说明它是柱子的底
        if (!has_prev[i]) {
            int curr = i;
            while (curr != 0) {
                cout << curr << (nxt[curr] == 0 ? "" : " ");
                curr = nxt[curr];
            }
            cout << "\n";
        }
    }
    
    return 0;
}

Dinic

网络流建图

这是一个动态加点的过程。我们从 $1$ 开始依次枚举球的数量 $num$ 。
构建二分图匹配的网络流模型：
- 设立源点 $S$ 和汇点 $T$ 。
- 对于每个球 $i$ ，拆分为两个点：左部点 $i$ 和右部点 $i + \text{OFFSET}$ 。
- 连边 $S \to i$ （容量1）。
- 连边 $i + \text{OFFSET} \to T$ （容量1）。
- 如果 $i < j$ 且 $i+j$ 是完全平方数，连边 $i \to j + \text{OFFSET}$ （容量1）。
每次增加一个球，就在残量网络上跑一次 maxFlow，累加最大流（即最大匹配数）。
当前需要的柱子数 = 当前球的总数 - 累计最大流。
如果需要的柱子数 $> n$ ，说明当前球放不下，答案即为 num - 1。

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-16 14:18:54
 */

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5; // 点
const int maxe = 2e6+5; // 边
const long long INF = 1e18;

// 存图的模板
struct linkList {
    typedef struct {int u,v,w,next;} edge;
    edge e[maxe];
    int h[maxn],edge_cnt=0;
    linkList(){
        reset();
    }

    void reset() {
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }

    //遍历点u 周围点
    template<typename U>
    void for_each(int u,U func){
        for(int i = h[u] ; i !=-1;i = e[i].next)
            func(e[i].u,e[i].v,e[i].w); //u v w
    }

    void add(int u,int v,int w=0){
        e[edge_cnt] = {u,v,w,h[u]};
        h[u] = edge_cnt++;
    }
    
    //下标访问
    edge& operator[](int i){ return e[i]; }

#ifdef __cpp_range_based_for
    struct UseEdge {
        using ReturnType = edge&; 
        static ReturnType get(linkList* p, int i) { return p->e[i]; }
    };
    struct UseAdj {
        using ReturnType = int;
        static ReturnType get(linkList* p, int i) { return p->e[i].v; }
    };

    template<typename Getter>
    struct BaseIterator {
        int i; linkList* p;
        BaseIterator(linkList* p, int i) : p(p), i(i) {}
        BaseIterator& operator++() { i = p->e[i].next; return *this; }
        bool operator!=(const BaseIterator& oth) { return i != oth.i; }
        typename Getter::ReturnType operator*() { return Getter::get(p, i); }
    };

    using Iterator    = BaseIterator<UseEdge>;
    using AdjIterator = BaseIterator<UseAdj>;

    template<typename IterT>
    struct BaseRange {
        int start; linkList* p;
        BaseRange(linkList* p, int start) : p(p), start(start) {}
        IterT begin() { return IterT(p, p->h[start]); }
        IterT end()   { return IterT(p, -1); }
    };

    BaseRange<Iterator> operator()(int u) { return BaseRange<Iterator>(this, u); }
    BaseRange<AdjIterator> adj(int u) { return BaseRange<AdjIterator>(this, u); }
#endif
} e;

// Dinic算法最大流模板
struct Dinic {
    vector<int> level, cur;
    int n;
    
    void init(int n) {
        e.edge_cnt = 0;
        memset(e.h, -1, sizeof(e.h));
        level.resize(n+5);
        cur.resize(n+5);
        this->n = n;
    }
    
    void addEdge(int u, int v, int cap) {
        e.add(u, v, cap);    
        e.add(v, u, 0);      
    }
    
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for(int i = e.h[u] ; ~i ;i = e[i].next) {
                int v = e[i].v, cap = e[i].w;
                if (cap > 0 && level[v] < 0) {
                    level[v] = level[u] + 1;
                    q.push(v);
                }
            }
        }
        return level[t] >= 0; 
    }
    
    long long dfs(int u, int t, long long preFlow) {
        if (u == t || preFlow == 0) return preFlow;
        long long flow = 0;
        for (int& cid = cur[u]; cid != -1; cid = e[cid].next) {
            auto& edge = e[cid]; 
            int to = edge.v;
            long long cap = edge.w;
            if (level[u] + 1 != level[to] || cap <= 0) continue;
            long long tr = dfs(to, t, min(preFlow, cap));
            e[cid].w -= tr ;     
            e[cid ^ 1].w += tr; 
            flow += tr;
            preFlow -= tr;
            if (preFlow == 0) break;
        }
        if (flow == 0) level[u] = -1;
        return flow;
    }
    
    long long maxFlow(int s, int t) {
        long long flow = 0;
        while (bfs(s, t)) { 
            for (int i = 0; i <= n; i++) {
                cur[i] = e.h[i]; 
            }
            flow += dfs(s, t, LLONG_MAX);
        }
        return flow;
    }
} dinic;

// --- 针对 P2765 的逻辑部分 ---

// 判断完全平方数
bool is_sq(int x) {
    int r = sqrt(x);
    return r * r == x;
}

// 记录每个球的下一个球是谁，用于输出
int nxt_ball[5005]; 
bool has_prev[5005]; // 标记球是否有前驱

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n;
    cin >> n;

    // 设定偏移量，用于构建二分图
    // 球 i 拆分为: 左边点 i, 右边点 i + OFFSET
    const int OFFSET = 2000; 
    const int S = 0;
    const int T = 4005;

    // 初始化Dinic，设置足够大的空间
    dinic.init(T + 10);

    int num_balls = 0;
    int total_flow = 0;

    while (true) {
        num_balls++;
        
        // 1. 在二分图中添加新球的相关边
        // 源点 -> 左部点 i
        dinic.addEdge(S, num_balls, 1);
        // 右部点 i -> 汇点
        dinic.addEdge(num_balls + OFFSET, T, 1);

        // 2. 尝试与之前的球建立连接
        for (int i = 1; i < num_balls; i++) {
            if (is_sq(i + num_balls)) {
                // 如果 i+num_balls 是完全平方数，
                // 则球 num_balls 可以放在球 i 上面
                // 对应二分图边: 左部点 i -> 右部点 num_balls
                dinic.addEdge(i, num_balls + OFFSET, 1);
            }
        }

        // 3. 在残量网络上继续跑最大流
        total_flow += dinic.maxFlow(S, T);

        // 4. 计算需要的最小柱子数
        // 最小路径覆盖 = 节点数 - 最大匹配数(最大流)
        int pillars_needed = num_balls - total_flow;

        if (pillars_needed > n) {
            num_balls--; // 恢复到上一个合法的状态
            break;
        }
    }

    cout << num_balls << "\n";

    // --- 恢复路径用于输出 ---
    // 遍历所有左部点 i
    memset(nxt_ball, 0, sizeof(nxt_ball));
    memset(has_prev, 0, sizeof(has_prev));

    for (int u = 1; u <= num_balls; u++) {
        // 遍历 u 的所有出边，找到流量为0（被占用）且指向右部点的边
        for (int i = e.h[u]; ~i; i = e[i].next) {
            int v = e[i].v;
            // 这是一个正向边(偶数索引) 且 满流(剩余容量w==0) 且 v是右部点
            if (i % 2 == 0 && e[i].w == 0 && v > OFFSET && v != T) {
                int real_v = v - OFFSET;
                nxt_ball[u] = real_v;
                has_prev[real_v] = true;
                break; // 一个点只能连一条出边
            }
        }
    }

    // 输出每根柱子
    for (int i = 1; i <= num_balls; i++) {
        // 如果 i 没有前驱，说明它是柱子最下面的球
        if (!has_prev[i]) {
            int curr = i;
            while (curr != 0) {
                cout << curr << (nxt_ball[curr] == 0 ? "" : " ");
                curr = nxt_ball[curr];
            }
            cout << "\n";
        }
    }

    return 0;
}

目录