#6003. 「网络流 24 题」魔术球
内存限制：256 MiB时间限制：1000 ms标准输入输出
题目类型：传统评测方式：Special Judge
上传者： 匿名
题目描述
假设有 n nn 根柱子，现要按下述规则在这 n nn 根柱子中依次放入编号为 1,2,3,4,⋯ 1, 2, 3, 4, \cdots1,2,3,4,⋯ 的球。
- 每次只能在某根柱子的最上面放球。
- 在同一根柱子中，任何 2 22 个相邻球的编号之和为完全平方数。
试设计一个算法，计算出在 n nn 根柱子上最多能放多少个球。
输入格式
文件第 1 11 行有 1 11 个正整数 n nn，表示柱子数。
输出格式
第一行是球数。接下来的 n nn 行，每行是一根柱子上的球的编号。
样例
样例输入
4样例输出
11
1 8
2 7 9
3 6 10
4 5 11数据范围与提示
1≤n≤55 1 \leq n \leq 551≤n≤55
把每个柱子看成一条路径，跑最小路径覆盖。
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct data {
int to,next,f;
}e[];
int head[],cnt;
void add(int u,int v,int f){e[cnt].to=v;e[cnt].next=head[u];e[cnt].f=f;head[u]=cnt++;}
int n,m,s,t;
bool vis[];
int q[],dis[];
bool bfs() {
memset(dis,-,sizeof(dis));
int h=,tail=;
q[h]=t;
dis[t]=;
while(h!=tail) {
int now=q[h++];if(h==) h=;
for(int i=head[now];i>=;i=e[i].next) {
if(dis[e[i].to]>-||!e[i^].f) continue;
dis[e[i].to]=dis[now]-;
q[tail++]=e[i].to;if(tail==) tail=;
}
}
return dis[s]>=-;
}
int dfs(int now,int a) {
int f=,flow=;
if(now==t) return a;
for(int i=head[now];i>=;i=e[i].next) {
int to=e[i].to;
if(dis[to]==dis[now]+&&e[i].f>) {
f=dfs(to,min(a,e[i].f));
flow+=f;
e[i].f-=f;
e[i^].f+=f;
a-=f;
if(a==) break;
}
}
return flow;
}
int num=;
int ans=;
int sum=;
int dinic() {
while(bfs()) {
sum+=dfs(s,);
}
return num-sum;
} bool work() {
num++;
add(s,num,);add(num,s,);add(num+,t,);add(t,num+,);
for(int i=;i<num;i++) {
if(sqrt(i+num)==(int)sqrt(i+num)) add(num,i+,),add(i+,num,);
}
if(dinic()<=n) return ;
else return ;
}
void pout(int x) {
vis[x]=;
printf("%d ",x);
for(int i=head[x+];i>=;i=e[i].next) {
if(e[i].f==&&!vis[e[i].to]){pout(e[i].to);return;}
}
return;
}
int main() {
memset(head,-,sizeof(head));
scanf("%d",&n);
s=,t=;
while(work()) ;
num--;
printf("%d\n",num);
memset(vis,,sizeof(vis));
vis[s]=vis[t]=;
for(int i=;i<=num;i++) {
if(!vis[i]){pout(i);printf("\n");}
}
}