Description

假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，...的球。
（1）每次只能在某根柱子的最上面放球。
（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。
试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4 根柱子上最多可放11 个球。
对于给定的n，计算在n根柱子上最多能放多少个球。

Input

多组数据输入.
每组输入1个正整数n，表示柱子数。

Output

每组输出n 根柱子上最多能放的球数。

Sample Input

4

Sample Output

11

Hint

Source

线性规划与网络流24题

你能不能再笨一点……→_→开始是卡在不理解为什么最小路径覆盖=顶点数-匹配数，看了那个裸的最小路径覆盖总算是明白了：

因为限制了左侧的每一个点和源点的流量都是1，就是限制了每个点只能用一次。因为每个点自身也可以算作是一个路径嘛，所以如果没有一个匹配的，那么路径数=顶点数，那么有匹配的话，路径数=顶点数-匹配数。

后来又卡在，每次加入一对点就要进行一次增广，但是黄大神的模板很明显node是连续的，你丫的是不是傻，dest设成1不就行了吗→_→输出依旧不会，遇到再说吧

/*************
nefu486
2016.1.18
1404k 260ms C++ (g++ 3.4.3) 
*************/
#include<cstdio>
using namespace std;
const int mm=1111111;
const int mn=11111;
const int oo=1000000000;
int node,src,dest,edge,ret;
int reach[mm],cap[mm],flow[mm],next[mm];
int head[mn],work[mn],dis[mn],q[mn];
bool square[mn]={0};
inline int min(int a,int b)
{
    return a<b?a:b;
}
inline void prepare(int _node,int _src,int _dest)
{
    node=_node,src=_src,dest=_dest;
    for(int i=0;i<node;++i)head[i]=-1;
    edge=ret=0;
}
inline void addedge(int u,int v,int c)
{
    reach[edge]=v,cap[edge]=c,flow[edge]=0,next[edge]=head[u],head[u]=edge++;
    reach[edge]=u,cap[edge]=0,flow[edge]=0,next[edge]=head[v],head[v]=edge++;
}
bool Dinic_bfs()
{
    int i,u,v,l,r=0;
    for(i=0;i<node;++i)dis[i]=-1;
    dis[q[r++]=src]=0;
    for(l=0;l<r;++l)
        for(i=head[u=q[l]];i>=0;i=next[i])
            if(flow[i]<cap[i]&&dis[v=reach[i]]<0)
            {
                dis[q[r++]=v]=dis[u]+1;
                if(v==dest)return 1;
            }
    return 0;
}
int Dinic_dfs(int u,int exp)
{
    if(u==dest)return exp;
    for(int &i=work[u],v,tmp;i>=0;i=next[i])
        if(flow[i]<cap[i]&&dis[v=reach[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,cap[i]-flow[i])))>0)
        {
            flow[i]+=tmp;
            flow[i^1]-=tmp;
            return tmp;
        }
    return 0;
}
int Dinic_flow()
{
    int i,delta;
    while(Dinic_bfs())
    {
        for(i=0;i<node;++i)work[i]=head[i];
        while((delta=Dinic_dfs(src,oo)))ret+=delta;
    }
    return ret;
}
void output(int u)
{
    q[u>>1]=1;
    for(int i=head[u],v;i>=0;i=next[i])
        if(q[v=reach[i]>>1]==0&&flow[i]==1)printf(" %d",v),output(v<<1);
}
int main()
{
    //freopen("input.txt","r",stdin);
   // freopen("output.txt","w",stdout);
    int i,n,u,v,ans;
    for(i=1;i*i<mn;++i)square[i*i]=1;
    while(scanf("%d",&n)!=-1)
    {
        ans=n;
        prepare(n+n+2,0,1);
        for(u=2;u<n+n+2;++u)
            if(u&1)addedge(u,dest,1);
            else addedge(src,u,1);
        for(u=1;u<=n;++u)
            for(v=u+1;v<=n;++v)
                if(square[u+v])addedge(u<<1,(v<<1)+1,1);
        while(ans<=Dinic_flow()+n)
        {
            ++ans;
            head[u=node++]=-1;
            head[v=node++]=-1;
            addedge(0,u,1);
            addedge(v,1,1);
            for(u=1;u<ans;++u)
                if(square[u+ans])addedge(u<<1,v,1);
        }
        printf("%d\n",ans-1);
        n=ans-1;
       /* prepare(n+n+2,0,1);
        for(u=2;u<n+n+2;++u)
        if(u&1)addedge(u,dest,1);
        else addedge(src,u,1);
        for(u=1;u<=n;++u)
            for(v=u+1;v<=n;++v)
                if(square[u+v])addedge(u<<1,(v<<1)+1,1);
        Dinic_flow();
        for(u=1;u<ans;++u)q[u]=0;
        for(u=1;u<ans;++u)
            if(!q[u])
            {
                printf("%d",u);
                output(u<<1);
                printf("\n");
            }*/
    }
}