[네트워크 흐름 24 문제] 마술 공 문제.

Description
n 개의 기둥 이 있다 고 가정 하면 다음 과 같은 규칙 에 따라 이 n 개의 기둥 에 번호 가 1, 2, 3 인 공 을 순서대로 넣 어야 한다.
(1) 매번 어떤 기둥 의 맨 위 에 만 공 을 놓 을 수 있다.
(2) 같은 기둥 에서 두 개의 인접 구 의 번호 의 합 은 완전 제곱 수 이다.
n 개의 기둥 에 최대 몇 개의 공 을 넣 을 수 있 는 지 계산 하 는 알고리즘 을 시험 적 으로 설계 하 다.예 를 들 어 기둥 4 개 에 최대 11 개의 공 을 넣 을 수 있다.
주어진 n 에 대해 n 개의 기둥 에 최대 몇 개의 공 을 넣 을 수 있 는 지 계산 합 니 다.
Input
파일 의 첫 줄 에 1 개의 정수 n 이 있 는데 기둥 수 를 나타 낸다.
Output
프로그램 이 실 행 될 때 n 개의 기둥 에 가장 많이 놓 을 수 있 는 공 수 와 해당 하 는 배치 방안 을 출력 합 니 다.파일 의 첫 줄 은 공 수 입 니 다.다음 n 줄 은 줄 마다 기둥 위의 공의 번호 입 니 다.
Sample Input

4

Sample Output

11
1 8
2 7 9
3 6 10
4 5 11

HINT

n<60

해제
네트워크 흐름 의 최대 흐름 매 거 진 답 s. 그림 에서 노드 1, 2,....................................................................매번 최대 흐름 a 를 한 번 구 합 니 다. 만약 a - 1 = n 이 라면 s - 1 은 바로 답 입 니 다.
code

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define N 10010
#define inf 0x7fffffff
using namespace std;
struct node
{
    int next,to,s;
};
node Edge[N*20];
const int m=5000;
const int T=10000;
int n,ans,s,tot=1;
int head[N];
int h[N],que[N];
bool used[N];
int to[N];

void add(int x,int y,int z)
{
    Edge[++tot].next=head[x];
    Edge[tot].to=y;
    Edge[tot].s=z;
    head[x]=tot;
}

void ins(int x,int y)
{
    add(x,y,1),add(y,x,0);
}

bool bfs()
{
    queue<int>Q;
    memset(h,-1,sizeof(h));
    h[0]=0;
    Q.push(0);
    while(!Q.empty())
    {
        int now=Q.front();
        Q.pop();
        for(int i=head[now];i;i=Edge[i].next)
        {
            if(h[Edge[i].to]==-1&&Edge[i].s)
            {
                h[Edge[i].to]=h[now]+1;
                Q.push(Edge[i].to);
            }
        }
    }
    if(h[T]==-1)return false;
    return true;
}

int dfs(int u,int f)
{
    if(u==T)return f;
    int used=0;
    for(int i=head[u];i;i=Edge[i].next)
    {
        if(!Edge[i].s||h[Edge[i].to]!=h[u]+1)continue;
        int w=f-used;
        w=dfs(Edge[i].to,min(w,Edge[i].s));
        Edge[i].s-=w;
        Edge[i^1].s+=w;
        used+=w;
        if(used==f)return f;
    }
    if(!used)h[u]=-1;
    return used;
}

void dinic()
{
    while(bfs())
        ans-=dfs(0,inf);
}

void getans()
{
    for(int i=1;ifor(int j=head[i];j;j=Edge[j].next)
        {
            if(Edge[j].s)continue;
            to[i]=Edge[j].to-m;
            break;
        }
    }
    for(int i=1;iif(used[i])continue;
        int t=i;
        while(t!=-m)
        {
            printf("%d ",t);
            used[t]=true;
            t=to[t];
        }
        puts("");
    }
}

int main()
{
    cin>>n;
    for(;;)
    {
        ans++,s++;
        for(int i=1;iif(sqrt(i+s)==(int)sqrt(i+s))
                ins(i,s+m);
        ins(0,s),ins(s+m,T);
        dinic();
        if(ans>n)break;
    }
    printf("%d
",s-1);
    getans();
    return 0;
}