原题链接：https://www.luogu.org/problemnew/show/P2765
曾经在模拟赛的时候做过弱化版，不需要输出方案。
其实加强版因为数据范围很小，模拟做也未尝不可，暴力算出n=55时最终答案也只有1567，拿二维数组存一下方案即可。
当然，这个题是由网络流做法的，虽然我的网络流做法只是模拟了一个贪心的过程。
贪心的正确性证明就请移步我的弱化版题解好啦:http://www.cnblogs.com/zeroform/p/7115044.html
对于一个球，有两种放法，独占一行或是连到一个柱子上。
把点拆成两个，记为x1与x2,两个点之间不连边，拆成的两个点处理不同情况，为保证合法，向汇点连一条边。
对于独占一行的情况，x1连向源点，
对于连到一个柱子上，其中能和它组成平方数的点y，x2向y1连一条边即可。
设i^i为他们的和。枚举i，i的范围是（sqrt（num）,sqrt(num<<1))
显然，i如果<=sqrt(num)的话，那么i*i-num<=0，显然不存在这样的球。
如果 i*i>=num<<1,那么这个球显然要在第num个球之后放下，不在此时的考虑范围之内，由此确定i的范围。
建完边之后，跑最大流即可，isap太难写，于是就用dinic了。
如果第num个点能够放在其他的柱子上的话，那么必然存在这样一个点a,有这样三条边:
s->a1 a1->num2 num2->t 所以在新图中，最大流不为零。
否则说明所有能与num组成平方数的数字a，上方都已经放了其他的球，图上s->a1这条边一定已经有1的流量流过，此时最大流为0，num必须另找一根柱子放下。
记录每根柱子的开头，dfs时记录它连向的点即可。
PS：打dfs的时候少打了一行，而且是最要紧的一行。。。写错之后，不但把建边搞乱了，查方案的时候也没法正常查。
（不知道怎么写《GG记录》，就写到这里好了）
GG记录链接（欣赏一下蒟蒻的zz错误吧）：http://www.cnblogs.com/zeroform/p/7678669.html
#include<cstdio> #include<cmath> #include<queue> #include<cstring> #include<iostream> using namespace std; const int inf=(1<<30); int n,tot,num,s,t=50003,cnt=1; struct edge { int u,v,w; }e[100005]; int l[100005],dis[100005],head[100005]; int nxt[100005],vis[100005]; void add(int u,int v) { e[++cnt].u=head[u];e[cnt].v=v; e[cnt].w=1;head[u]=cnt; e[++cnt].u=head[v];e[cnt].v=u; e[cnt].w=0;head[v]=cnt; } int dfs(int x,int f) { if(x==t) return f; for(int i=head[x];i!=-1;i=e[i].u) { int tmp=e[i].v; if(dis[tmp]==dis[x]+1&&e[i].w>0) { int d=dfs(tmp,min(f,e[i].w)); if(!d) continue;//就是这一行让我debug1.5h e[i].w-=d; e[i^1].w+=d; if(tmp!=t) nxt[x>>1]=(tmp>>1); return d; } } return 0; } int bfs() { memset(dis,0,sizeof(dis)); queue<int>q; q.push(s);dis[s]=1; while(!q.empty()) { int tmp=q.front();q.pop(); for(int i=head[tmp];i!=-1;i=e[i].u) { int p=e[i].v; if(dis[p]||e[i].w<=0) continue; dis[p]=dis[tmp]+1; q.push(p); } } return dis[t]; } int dinic() { int ans=0; while(bfs()) { while(1) { int p=dfs(s,inf); if(p==0) break; ans+=p; } } return ans; } int main() { scanf("%d",&n); memset(head,-1,sizeof(head)); while(tot<=n) { num++; add(s,num<<1); add(num<<1|1,t); for(int i=sqrt(num)+1;i*i<(num<<1);i++) { add((i*i-num)<<1,num<<1|1); } if(!dinic()) l[++tot]=num; } num--; printf("%d ",num); for(int i=1;i<=n;i++) { if(vis[l[i]]) continue; int st=l[i];vis[st]=1; while(st) { printf("%d ",st); st=nxt[st];vis[st]=1; } printf(" "); } return 0; }