[Luogu2765]魔术球问题

# 题意 有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，...的球： - 每次只能在某根柱子的最上面放球 - 在同一根柱子中，任何2个相邻球的编号之和为完全平方数 求在n根柱子上最多能放多少个球 <!--more--> # 分析 把球看做点，显然两个和为完全平方数的球$x,y(x<y)$可以从$x$向$y$连一条边 但是，题目中的点是动态增加的，因此我们需要动态加边实现网络流 首先有一个贪心的思路（证明先咕着），就是能放就放，实在不行再开新的柱子 题目要求每个球只能使用一次且要顺次放入，那么考虑拆点 既然是动态加点，那么我们将$u$拆后的点标为$u\times 2$和$u\times 2+1$. 将$u$拆成$u_{s}$和$u_{t}$，源点与$u_s$直接连接，$u_t$与汇点直接连接 然后对于每个$v(v<u,u+v=k^2,k\in \mathbb{Z})$，我们将$v_s$和$u_t$连一条边 如果一个点$u$不在某一个柱子的顶端，那么$f(s,u_s)=0$，也就不会重复使用$u$；如果$u$在某个柱子的顶端，那么显然$f(s,u_s)>0$，这个点就可以使用 然后在图上跑最大流即可。如果没有增加的流，就新开一个柱子（其实不需要特别操作，记录一下这个柱子的开头即可） 答案的输出，在最大流的过程中维护链表即可 # 代码 ```cpp #include<cstdio> #include<cmath> #include<queue> #include<cstring> using namespace std; const int N=10000,M=2e6; int n,m,s,t,n1,INF=0x3f3f3f3f; struct qxx{int nex,t,v;}; qxx e[M]; int h[N],cnt=1; void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;} void add_flow(int f,int t,int v){add_path(f,t,v);add_path(t,f,0);} int rk[N]; bool bfs(){ memset(rk,0,sizeof(rk)); queue<int> q; q.push(s),rk[s]=1; while(q.size()){ int u=q.front();q.pop(); for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v; if(w&&!rk[v])rk[v]=rk[u]+1,q.push(v); } } return rk[t]; } int suf[N]; int dinic(int u,int flow){ if(u==t)return flow; for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v; if(w<=0||rk[v]!=rk[u]+1)continue; int x=dinic(v,min(flow,w)); if(x)return e[i].v-=x,e[i^1].v+=x,(u==t?0:suf[u>>1]=(v>>1)),x;//>>1变回原来的编号 else rk[v]=0; } return 0; } int ans[N],ant;//链表表头 int main(){ scanf("%d",&n1); s=0,t=N-1; while(ant<=n1){ ++n;//增加一个球 add_flow(s,n<<1,1);add_flow(n<<1|1,t,1);//分点 for(int i=sqrt(n)+1;i*i<(n<<1);i++)add_flow((i*i-n)<<1,n<<1|1,1); int flow=0; while(bfs())for(int i=dinic(s,INF);i;i=dinic(s,INF))flow+=i; if(!flow)ans[++ant]=n;//没有更新最大流，则新开一个结点 } --ant,--n; printf("%d\n",n); for(int i=1;i<=ant;i++){ for(int j=ans[i];j!=t&&j!=t>>1&&j!=0;j=suf[j])printf("%d ",j); puts(""); } return 0; } ```