问题描述：
假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为 1，2，3，4......的球。
（1）每次只能在某根柱子的最上面放球。
（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。
试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4 根柱子上最多可
放11个球。
′编程任务：
对于给定的n，计算在 n根柱子上最多能放多少个球。
′数据输入：
文件第1 行有 1个正整数n，表示柱子数。
′结果输出:
文件的第一行是球数。
数据规模
n<=60 保证答案小于1600
输入文件示例
4
输出文件示例
11
方案如下
1 8
2 7 9
3 6 10
4 5 11
每一行表示一个柱子上的球
/* 看到这道题我一下子想到二分答案，拆点建图，然后不会判断了，看了看黄学长的代码，不是很懂。 然后自己敲了一遍，竟然超时了一个点，我的天！明天接着搞…… */ #include<cstdio> #include<cstring> #include<iostream> #include<cmath> #define N 3210 #define inf 1000000000 using namespace std; int head[N],dis[N],q[N],cnt=1,S,T,flow; struct node{ int v,f,pre; };node e[N*N]; void add(int u,int v,int f){ e[++cnt].v=v;e[cnt].f=f;e[cnt].pre=head[u];head[u]=cnt; e[++cnt].v=u;e[cnt].f=0;e[cnt].pre=head[v];head[v]=cnt; } bool bfs(){ for(int i=1;i<=T;i++)dis[i]=inf; int h=0,t=1;q[1]=S;dis[S]=0; while(h<t){ int u=q[++h]; for(int i=head[u];i;i=e[i].pre){ int v=e[i].v; if(e[i].f&&dis[u]+1<dis[v]){ dis[v]=dis[u]+1; if(v==T)return true; q[++t]=v; } } } if(dis[T]==inf)return false; return true; } int dinic(int now,int f){ if(now==T)return f; int rest=f; for(int i=head[now];i;i=e[i].pre){ int v=e[i].v; if(e[i].f&&dis[v]==dis[now]+1){ int t=dinic(v,min(rest,e[i].f)); if(!t)dis[v]=0; e[i].f-=t; e[i^1].f+=t; rest-=t; } } return f-rest; } bool check(int n){ memset(head,0,sizeof(head));cnt=1; S=0;T=n*2+1; for(int i=1;i<=n;i++){ add(S,i,1);add(i+n,T,1); } for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++){ int t=sqrt(i+j); if(t*t==i+j)add(i,j+n,1); } int max_flow=0; while(bfs())max_flow+=dinic(S,inf); if(flow+max_flow<n)return false; return true; } int main(){ freopen("balla.in","r",stdin); freopen("balla.out","w",stdout); scanf("%d",&flow); if(!flow){ printf("0");return 0; } int l=1,r=1600,ans; while(l<=r){ int mid=(l+r)/2; if(check(mid))l=mid+1,ans=mid; else r=mid-1; } printf("%d",ans); return 0; }
原文：http://www.cnblogs.com/harden/p/6257834.html