https://www.luogu.com.cn/problem/P2765
题意概述
有 \(n\) 根柱子，依次放编号为 $1,2,\cdots $ 的球，每次只能在一根柱子的最上方放球，同一根柱子任意相邻两个球的编号之和必须是完全平方数。
求最多能放多少个球，并构造方案。
思路
考虑用有向边刻画同一根柱子的约束关系，如果 \(u\lt v\)，且 \(u+v\) 是完全平方数，连 \(u\) 到 \(v\) 的边，建出是 \(DAG\)。可以发现，这是路径覆盖问题。
考虑二分答案，记球的数量为 \(V\)，只需要判断最小路径覆盖是否 \(\le n\) 即可。
求最小路径覆盖是个经典问题，具体做法是，把每个点拆成两个出点和入点，对原图中的边 \(u\)->\(v\)，将 \(u\) 的出点连 \(v\) 的入点，然后求最大匹配即可。最小路径覆盖 \(=\) 顶点数 \(-\) 最大匹配。
直觉来看，二分的上界不会太大，同时边的数量也较少，姑且取 \(V^2\) 不会超时的值。代码中取了 \(5005\)。
时间复杂度 \(\mathcal{O}(K^2 \log K)\)，\(K\) 是二分的上界。建图是 \(\mathcal{O}(V^2)\)，边数大概是 \(V\sqrt{V}\)，所以 \(dinic\) 求最大匹配是 \(\mathcal{O}(V^2)\)，单次二分就是 \(\mathcal{O}(V^2)\)。
代码
//author:kzssCCC#include <bits/stdc++.h>
using namespace std;
using ll = long long;class dinic{
public:const ll INF = 9e18;int n,s,t;vector<vector<array<ll,4>>> adj;ll mxf;vector<int> cur,depth;dinic(int _n,int _s,int _t){n = _n;s = _s;t = _t;adj = vector<vector<array<ll,4>>>(n+1);}void add(int u,int v,ll w){adj[u].push_back({w,1,(int)adj[v].size(),v});adj[v].push_back({0,0,(int)adj[u].size()-1,u});}bool bfs(){depth = vector<int>(n+1,-1);queue<int> q;depth[s] = 0;q.push(s);while (!q.empty()){int u = q.front();q.pop();for (auto& [w,flag,rev,v]:adj[u]){if (w>0 && depth[v]==-1){depth[v] = depth[u]+1;q.push(v);}}}return depth[t]!=-1;}ll dfs(int u,ll mf){if (u==t) return mf;ll sum = 0;int len = adj[u].size();for (int& i=cur[u];i<len;i++){auto& [w,flag,rev,v] = adj[u][i];if (w>0 && depth[v]==depth[u]+1){ll f = dfs(v,min(mf,w));sum += f;mf -= f;w -= f;adj[v][rev][0] += f;if (mf==0) break;}}return sum;}void work(){mxf = 0;while (bfs()){cur = vector<int>(n+1);mxf += dfs(s,INF);}}
};const ll INF = 9e18;void solve(){int n;cin >> n;auto pd = [&](int x){int f1 = (int)sqrt(x);int f2 = ceil(sqrt(x));return f1*f1==x || f2*f2==x;};auto check = [&](int mid)->vector<vector<int>>{int N = mid*2+2;int s = N-1;int t = N;dinic dn(N,s,t);for (int i=1;i<=mid;i++){ for (int j=i+1;j<=mid;j++){if (pd(i+j)){dn.add(i,j+mid,1);}}dn.add(s,i,1);dn.add(i+mid,t,1);}dn.work();if (mid-dn.mxf>n){return {};}vector<int> next(mid+1,-1),ing(mid+1);for (int u=1;u<=mid;u++){for (auto& [w,flag,rev,v]:dn.adj[u]){if (flag==1 && w==0){next[u] = v-mid;ing[v-mid]++;}}}int x = 1;vector<vector<int>> res(n+1);vector<bool> vis(mid+1,false);for (int i=1;i<=mid;i++){if (!vis[i] && ing[i]==0){int u = i;while (u!=-1){vis[u] = true;res[x].push_back(u);u = next[u];}x++;}}int y = 1;while (x<=n){while (res[y].size()==1){y++;} res[x++].push_back(res[y].back());res[y].pop_back(); }return res;};int l=1,r=5005;while (l<=r){int mid = l+(r-l>>1);if (!check(mid).empty()){l = mid+1;}else{r = mid-1;}}int mx = r;auto res = check(mx);cout << mx << '\n';for (int i=1;i<=n;i++){for (auto& v:res[i]){cout << v << ' ';}cout << '\n';}
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t = 1;// cin >> t;while (t--) solve();return 0;
}