传送门
题目描述
«问题描述：
假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，...的球。
（1）每次只能在某根柱子的最上面放球。
（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。
试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4 根柱子上最多可放11 个球。
«编程任务：
对于给定的n，计算在n根柱子上最多能放多少个球。
输入输出格式
输入格式：
第1 行有1个正整数n，表示柱子数。
输出格式：
程序运行结束时，将n 根柱子上最多能放的球数以及相应的放置方案输出。文件的第一行是球数。接下来的n行，每行是一根柱子上的球的编号。
输入输出样例
输入样例#1：
4
输出样例#1：
11
1 8
2 7 9
3 6 10
4 5 11
题解
枚举答案，一直到全部连边，一直枚举到最小路径覆盖数刚好超过n为s,那么s-1即为最优解
code:
//By Menteur_Hxy
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define M(a,b) memset(a,(b),sizeof(a))
const int MAX=200000;
const int INF=0x3f3f3f3f;
const int T=10000;
int n,ans,cnt=1,s;
int nxt[MAX],wi[MAX],to[MAX],head[MAX];
int de[MAX],qu[MAX],cur[MAX],fa[MAX],mark[MAX];
int dfs(int x,int f) {
if(x==T) return f;
int w,used=0;
for(register int i=head[x];i;i=nxt[i])
if(wi[i]&&de[to[i]]==de[x]+1) {
w=dfs(to[i],min(f-used,wi[i]));
wi[i]-=w,wi[i^1]+=w; used+=w;
if(used==f) return f;
}
if(!used) de[x]=-1;
return used;
}
bool bfs() {
int h=0,t=1,now;
M(de,-1); de[0]=qu[0]=0;
while(h<=t)
for(register int i=head[now=qu[h++]];i;i=nxt[i])
if(wi[i]&&de[to[i]]==-1)
de[to[i]]=de[now]+1,qu[t++]=to[i];
if(de[T]==-1) return 0;
return 1;
}
#define dinic() while(bfs()) ans-=dfs(0,INF)
#define add(a,b,c) nxt[++cnt]=head[a],wi[cnt]=c,to[cnt]=b,head[a]=cnt
#define insert(a,b,c) add(a,b,c),add(b,a,0)
int main() {
scanf("%d",&n);
while(1) {
ans++;s++;
for(register int i=1;i<s;i++)
if(sqrt(i+s)==(int)(sqrt(i+s)))
insert(i,s+5000,1);
insert(0,s,1); insert(s+5000,T,1);
dinic();
if(ans>n) break;
} printf("%d
",s-1);
for(register int i=1;i<s;i++)
for(register int j=head[i];j;j=nxt[j])
if(!wi[j]) {fa[i]=to[j]-5000;break;}
for(register int i=1;i<s;i++) {
if(mark[i]) continue; int t=i;
while(t!=-5000) {
mark[t]=1;
printf("%d ",t);
t=fa[t];
}
puts("");
}
return 0;
}