传送门：>Here<
题意：有N根柱子，并且有连续编号的小球依次放入。要求后来的小球只能放在某根柱子最上面的小球上面，并且必须满足这两个小球的编号之和为完全平方数。求最多能放几个小球？
思路分析
真是好题~
由于N的范围不到60，所以我们可以采用非常暴力的做法。
把问题反过来考虑，如果有N个球，最少用几个柱子？考虑DAG的最小路径覆盖——将能够放在一起的（即和为完全平方数）的小球之间连有向边（小的连到大的），这样的一张图的最小路径覆盖也就是需要的最少的柱子。因此问题就转化为了最小路径覆盖问题——拆点+最大流。
因此我们只需要枚举小球的数量，每一次把新来的小球拆成两个，分别连源点和汇点，并且扫一遍连完全平方数。然后每一次做一遍Dinic（千万注意flow要清零），判断是否够N根柱子。如果大于N，则跳出。去除这一次多余的边重新建图跑Dinic，输出方案即可
现在有一个问题，为什么柱子的需求量与小球数量成正比？其实很简单，新加进去一个球并没有可能性让柱子的数量减少。
Code
典型的细节题：注意在统计的时候由于编号是偶数，每次+2，而不是*2！
另外，去除最后多余的边是个问题。我们可以考虑重新弄一张邻接表，每一次如果成功就把所有边赋值一遍。注意first随时都会修改，所以所有点的first都需要更新。最后在记录sec的时候要记得-1，分清奇偶性。
/*By DennyQi*/ #include <cstdio> #include <queue> #include <cstring> #include <algorithm> #define r read() #define Max(a,b) (((a)>(b)) ? (a) : (b)) #define Min(a,b) (((a)<(b)) ? (a) : (b)) using namespace std; typedef long long ll; const int MAXN = 100010; const int MAXM = 300010; const int INF = 1061109567; inline int read(){ int x = 0; int w = 1; register int c = getchar(); while(c ^ '-' && (c < '0' || c > '9')) c = getchar(); if(c == '-') w = -1, c = getchar(); while(c >= '0' && c <= '9') x = (x << 3) +(x << 1) + c - '0', c = getchar(); return x * w; } int P,N,S,T,x,y,match; int first[MAXM*2],nxt[MAXM*2],to[MAXM*2],cap[MAXM*2],flow[MAXM*2],num_edge=-1; int _first[MAXM*2],_nxt[MAXM*2],_to[MAXM*2],_cap[MAXM*2],_flow[MAXM*2],last=-1; int level[MAXN],cur[MAXN],pre[MAXN],sec[MAXN]; queue <int> q; inline void add(int u, int v, int c, int f){ to[++num_edge] = v; cap[num_edge] = c; flow[num_edge] = f; nxt[num_edge] = first[u]; first[u] = num_edge; } inline void AddEdge(int u, int v){ add(u*2, v*2+1, 1, 0); add(v*2+1, u*2, 0, 0); } inline bool BFS(){ memset(level, 0, sizeof(level)); while(!q.empty()) q.pop(); q.push(S); level[S] = 1; int u,v; while(!q.empty()){ u = q.front(); q.pop(); for(int i = first[u]; i != -1; i = nxt[i]){ v = to[i]; if(!level[v] && cap[i]-flow[i] > 0){ level[v] = level[u] + 1; q.push(v); } } } return level[T] != 0; } int DFS(int u, int a){ if(u == T || a == 0) return a; int ans = 0, v, _f; for(int& i = cur[u]; i != -1; i = nxt[i]){ v = to[i]; if(level[u]+1 == level[v] && cap[i]-flow[i] > 0){ _f = DFS(v, Min(a, cap[i]-flow[i])); ans += _f, a -= _f; flow[i] += _f, flow[i^1] -= _f; if(a == 0) break; } } return ans; } inline void Dinic(){ match = 0; while(BFS()){ for(int i = S; i <= T; ++i) cur[i] = first[i]; match += DFS(S, INF); } match = N - match; } int main(){ P=r; S = 0, T = 12345; memset(first,-1,sizeof(first)); for(N = 1; ; ++N){ last = num_edge; memset(flow, 0, sizeof(flow)); for(int i = 1; i < N; ++i){ if(i*i - N >= N) break; if(i*i > N){ AddEdge(i*i-N, N); } } add(S, N*2, 1, 0), add(N*2, S, 0, 0); add(N*2+1, T, 1, 0), add(T, N*2+1, 0, 0); Dinic(); if(match > P){ --N; break; } for(int i = 0; i <= num_edge; ++i){ _nxt[i] = nxt[i]; _cap[i] = cap[i]; _flow[i] = flow[i]; _to[i] = to[i]; } for(int i = 0; i <= N*2+4; ++i){ _first[i] = first[i]; } _first[T] = first[T]; } printf("%d ", N); for(int i = 2; i <= 2*N; i += 2){ for(int j = _first[i]; j != -1; j = _nxt[j]){ if(_cap[j]-_flow[j]==0 && _cap[j]==1){ pre[_to[j]-1] = i; sec[i] = _to[j]-1; } } } for(int i = 2; i <= 2*N; i += 2){ if(pre[i] == 0){ int u = i; while(sec[u] != 0){ printf("%d ", u/2); u = sec[u]; } printf("%d ", u/2); } } return 0; }