这道题目，一眼看上去，并不能用网络流做
但是我们发现，如果将每个点拆成x和x'
然后x连源点，x'连汇点 都用容量为一的边
再然后是找这个数可以与那个数组成完全平方数，然后将这个数i与x'连边
每加入一个点就跑一次最大流
那么如果可以塞进原柱，那么最大流就得到1否则为0
那么我们在得到0的时候新建柱子即可
另外，我们要注意
在判断完全平方数的时候
sqrt(ge+i)*sqrt(ge+i)==ge+i
这样判断在Windows下是正确的
但在Linux下要写成(int)sqrt(ge+i)*sqrt(ge+i)==ge+i
总体实现如下：
#include <algorithm> #include <iostream> #include <cmath> #include <cstring> #include <map> #include <string> #include <vector> #include <queue> #include <stack> #include <cstdio> #include <cstdlib> using namespace std; typedef long long ll; inline ll read() {register ll p(1),a(0);register char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();if(ch=='-') p=-1,ch=getchar();while(ch>='0'&&ch<='9') a=a*10+ch-48,ch=getchar();return a*p; } const int N=100100; queue<int> Q; int src=0,n,num,st=50014,d[N],head[N],pre[N],cnt=1,ge,jl[N],book[N]; struct EDGE{int nxt,val,to;}e[N]; void add(int u,int v,int w){e[++cnt]=(EDGE){head[u],w,v};head[u]=cnt;} int BFS() {while(!Q.empty()) Q.pop();Q.push(src);memset(d,-1,sizeof(d));d[src]=0;int u;while(!Q.empty()){u=Q.front();Q.pop();for(int i=head[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to) if(e[i].val&&d[v]==-1){d[v]=d[u]+1;if(v==st) return 1;Q.push(v);}}return 0; } int DFS(int u,int flow) {if(u==st||flow==0) return flow;int res=flow,tt;for(int i=head[u],v=e[i].to;i&&res;i=e[i].nxt,v=e[i].to) if(e[i].val&&d[v]==d[u]+1){tt=DFS(v,min(res,e[i].val));if(!tt) d[v]=-1;if(tt&&v!=st) pre[u>>1]=v>>1;e[i].val-=tt;e[i^1].val+=tt;res-=tt;}return flow-res; } int Dinic() {int all=0;while(BFS()) all+=DFS(src,0x3f3f3f3f);return all; } int main() {// freopen("input","r",stdin);// freopen("output","w",stdout);n=read();while(num<=n){++ge;add(src,ge<<1,1);add(ge<<1,src,0);add(ge<<1|1,st,1);add(st,ge<<1|1,0);for(int i=1;i<ge;++i) if((int)sqrt(ge+i)*sqrt(ge+i)==ge+i) {add(i<<1,ge<<1|1,1);add(ge<<1|1,i<<1,0);}if(!Dinic()) jl[++num]=ge;}printf("%d\n",--ge);for(int i=1;i<=n;i++){if(book[jl[i]]) continue;int tt=jl[i];book[tt]=1;while(tt) printf("%d ",tt),book[tt=pre[tt]]=1;printf("\n");}return 0; }
