https://www.luogu.org/problemnew/show/P2765
看到这一题第一眼想到：这不是二分最大流吗，后来发现还有一种更快的方法。
首先如果知道要放多少个球求最少的柱子，很显然是一道最小点路径覆盖的题，将一个点拆成u,v两个点，u和S相连，v和T相连，之后的有向边i,就用ui和vj相连即可。
但是这题首先不知道有多少个球，所以考虑依次加入点以及和这个点相关的边，然后在残余网络上跑新的最大流，如果可以跑出流量来意味着这个点成功在现有的柱子上按排上了，如果跑不出来说明按排不上，需要重新开一根柱子放这个点。
直到跑到答案k的时候，柱子数超过了n，要的答案就是k - 1，至于方案，只要在最后的残余网络图上面搜索一下每个点的前驱即可。
#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Sca2(x,y) scanf("%d%d",&x,&y) #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d ", x) #define Prl(x) printf("%lld ",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();} while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;} const double eps = 1e-9; const int maxn = 3010; const int maxm = 80010; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,K; int a[maxn]; struct Edge{ int to,next,cap,flow; Edge(){} Edge(int to,int next,int cap,int flow):to(to),next(next),cap(cap),flow(flow){} }edge[maxm * 2]; int head[maxn * 2],dis[maxn * 2],pre[maxn * 2],nxt[maxn * 2],vis[maxn * 2]; int n,s,tot,t; void init(int N,int S,int T){ n = N;s = S;t = T; for(int i = 0 ; i <= n ; i ++) head[i] = -1; tot = 0; } void add(int u,int v,int w){ edge[tot] = Edge(v,head[u],w,0); head[u] = tot++; edge[tot] = Edge(u,head[v],0,0); head[v] = tot++; } bool BFS(){ for(int i = 0 ; i <= n; i ++) dis[i] = -1; queue<int>Q; dis[s] = 0; Q.push(s); while(!Q.empty()){ int u = Q.front(); Q.pop(); for(int i = head[u]; ~i ; i = edge[i].next){ int v = edge[i].to; if(~dis[v] || edge[i].cap <= edge[i].flow) continue; dis[v] = dis[u] + 1; Q.push(v); } } return ~dis[t]; } int dfs(int u,int a){ if(u == t || !a) return a; int flow = 0; for(int &i = pre[u]; ~i ; i = edge[i].next){ int v = edge[i].to; if(dis[u] + 1 != dis[v]) continue; int f = dfs(v,min(a,edge[i].cap - edge[i].flow)); if(!f) continue; a -= f; flow += f; edge[i].flow += f; edge[i ^ 1].flow -= f; } return flow; } int maxflow(){ int flow = 0; while(BFS()){ for(int i = 0 ; i <= n ; i ++) pre[i] = head[i]; flow += dfs(s,INF); } return flow; } void search(int t){ for(int i = 1; i <= t; i ++){ for(int j = head[i]; ~j ; j = edge[j].next){ int v = edge[j].to; if(v == s) continue; if(edge[j].flow){ nxt[i] = v - maxn; vis[v - maxn] = 1; } } } for(int i = 1; i <= t; i ++){ if(!vis[i]){ for(int j = i; j; j = nxt[j]){ printf("%d ",j); } puts(""); } } } int main(){ Sca(N); for(int i = 1; i <= 60; i ++) a[i] = i * i; int S = 6001,T = 6002; init(6002,S,T); int num = 0,k; int cnt = 1; for(k = 1;num <= N; k ++){ while(k + k > a[cnt + 1]) cnt++; add(S,k,1); add(k + maxn,T,1); for(int i = cnt ; i >= 1; i --){ if(a[i] - k <= 0) break; add(a[i] - k,k + maxn,1); } if(!maxflow()) num++; } k-=2; num--; Pri(k); search(k); return 0; }