题目描述

假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，…的球。

（1）每次只能在某根柱子的最上面放球。

（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。

试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4 根柱子上最多可放11 个球。

«编程任务：

对于给定的n，计算在n根柱子上最多能放多少个球。

思路

从小到大枚举答案，如果最小路径覆盖大于柱子数的话就退出，然后重新跑一边输出路径

#include 
#include 
#include 
#include 
#define maxn 100001
#define E 40000
#define mid 5001
#define fill(x,y) memset(x,y,sizeof(x))
#define min(x,y) x t;
    t.push(x);
    fill(state,63);
    state[x]=0;
    while (!t.empty())
    {
        int tt=t.front();t.pop();
        for (int i=ls[tt];i;i=e[i].next)
        {
            if (e[i].w>0&&state[tt]+10)
        {
            int d=find(e[i].y,min(mn,e[i].w));
            if (d>0)
            {
                e[i].w-=d;
                e[e[i].rev].w+=d;
                vis[x]=e[i].y;
                return d;
            }
        }
    return 0;
}
int main()
{
    int n;
    scanf("%d",&n);
    int t=0,ans=0;
    while (1)//从小到大枚举答案
    {
        t++;
        for (int i=1;in)//如果最小路径覆盖大于柱子数就退出
        {
            ans=t-1;
            break;
        }
    }
    fill(ls,0);
    fill(vis,0);
    maxE=0;
    for (int i=1;i<=ans;i++)
        add(0,i,1),add(i+mid,E,1);
    for (int j=1;j<=ans;j++)
        for (int i=1;i<=j-1;i++)
            if (sqrt(i+j)==(int)sqrt(i+j))
                add(i,j+mid,1);
    int l=0;
    while (bfs(0))//在跑一边求出路径
        l+=find(0,INF);
    printf("%d\n",ans);
    for (int i=1;i<=ans;i++)//输出路径
    {
        if (vis[i]!=0)
        {
            int t=i;
            do
            {
                if (t>mid) t-=mid;
                printf("%d ",t);
                int x=vis[t];
                vis[t]=0;
                t=x;
            }
            while (t!=0);
            printf("\n");
        }
    }
}