枚举放的球,先假设新建柱子,拆成两个点,第一个点连S,表示后面还可以放;第二个连T表示放到其他柱子上;再枚举放过的数和它是否组成完全平方数,枚举的数的第一个点向它的第二个点连边,表示这个球可以放到其他球上,容量都为一
每次跑最大流出来的表示会消掉的柱子个数,如果此时球-消去的比n大则break输出答案
# include <stdio.h>
# include <stdlib.h>
# include <iostream>
# include <string.h>
# include <math.h>
# define ll long long
# define RG register
# define IL inline
# define mem(a, b) memset(a, b, sizeof(a))
# define Max(a, b) (((a) > (b)) ? (a) : (b))
# define Min(a, b) (((a) < (b)) ? (a) : (b))
# define Sqr(a) ((a) * (a))
using namespace std;
IL int Get(){
RG char c = '!'; RG int x = 0, z;
for(; c > '9' || c < '0'; c = getchar()) z = (c == '-') ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
return x * z;
}
const int MAXN = 10001, MAXM = 200001, INF = 2147483647;
int n, m, ft[MAXN], cnt, ans, level[MAXN], Q[MAXM], cur[MAXN], match[MAXN], vis[MAXN];
struct Edge{
int to, nt, f;
} edge[MAXM];
IL void Add(RG int u, RG int v, RG int f){
edge[cnt] = (Edge){v, ft[u], f}; ft[u] = cnt++;
}
IL bool Bfs(RG int S, RG int T){
mem(level, 0);
RG int head = 0, tail = 0;
level[S] = 1; Q[0] = S;
while(head <= tail){
RG int u = Q[head++];
for(RG int e = ft[u]; e != -1; e = edge[e].nt){
RG int v = edge[e].to;
if(!level[v] && edge[e].f){
level[v] = level[u] + 1;
Q[++tail] = v;
}
}
}
return level[T];
}
IL int Dfs(RG int u, RG int T, RG int maxf){
if(u == T) return maxf;
RG int ret = 0;
for(RG int &e = cur[u]; e != -1; e = edge[e].nt){
RG int v = edge[e].to;
if(level[v] == level[u] + 1 && edge[e].f){
RG int f = Dfs(v, T, Min(maxf - ret, edge[e].f));
edge[e].f -= f; edge[e ^ 1].f += f;
ret += f; match[u] = v;
if(ret == maxf) break;
}
}
if(!ret) level[u] = 0;
return ret;
}
int main(){
mem(ft, -1);
n = Get();
RG int S = 0, T = 4000, num = 0;
while(++num){
Add(S, num, 1); Add(num, S, 0);
Add(num + 2000, T, 1); Add(T, num + 2000, 0);
for(RG int i = 1; i < num; i++)
if(Sqr((int)sqrt(i + num)) == i + num)
Add(i, num + 2000, 1), Add(num + 2000, i, 0);
while(Bfs(S, T)){
for(RG int i = S; i <= T; i++)
cur[i] = ft[i];
ans += Dfs(S, T, INF);
}
if(num - ans > n){
printf("%d
", num - 1);
break;
}
}
for(RG int i = 1; i < num; i++)
if(!vis[i]){
RG int j = i;
while(j){
if(j != 2000 && j != 4000) j > 2000 ? printf("%d ", j -= 2000) : printf("%d ", j);
vis[j] = 1;
j = match[j];
}
printf("
");
}
return 0;
}