题解:
个人认为网络流二十三题中比较有意思的一道。
先枚举球数。
每加一个球,从$S$向$xi$连一条容量为$1$的边,从$yi$向$T$连一条容量为$1$的边。
然后从$xi$向满足$i+j$为完全平方数的$yj$连容量为$1$的边。
在残余网络上跑$EK$或$Dinic$,如果得到的最大流为$0$,说明失配,需要重开一柱。
其实就是动态的二分图匹配。
每个球后面只能接一个球嘛。
代码:
#include<queue> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 6050 const int inf = 0x3f3f3f3f; int n,S,T; int m,tot; int hed[N],cnt=-1,cur[N]; struct EG { int to,nxt,w; }e[2000050]; void ae(int f,int t,int w) { e[++cnt].to = t; e[cnt].nxt = hed[f]; e[cnt].w = w; hed[f] = cnt; } int dep[N]; bool vis[N]; queue<int>q; bool bfs() { memset(dep,0x3f,sizeof(dep)); memcpy(cur,hed,sizeof(cur)); dep[S] = 0; vis[S] = 1; q.push(S); while(!q.empty()) { int u = q.front(); q.pop(); for(int j=hed[u];~j;j=e[j].nxt) { int to = e[j].to; if(e[j].w&&dep[to]>dep[u]+1) { dep[to] = dep[u]+1; if(!vis[to]) { vis[to] = 1; q.push(to); } } } vis[u] = 0; } return dep[T]!=inf; } int dfs(int u,int lim) { if(u==T||!lim)return lim; int fl=0,f; for(int j=hed[u];~j;j=e[j].nxt) { int to = e[j].to; if(dep[to]==dep[u]+1&&(f=dfs(to,min(lim,e[j].w)))) { fl+=f,lim-=f; e[j].w-=f,e[j^1].w+=f; if(!lim)break; } } return fl; } int dinic() { int ret = 0; while(bfs())ret+=dfs(S,inf); return ret; } bool use[N]; void print(int u) { printf("%d ",u); for(int j=hed[u<<1|1];~j;j=e[j].nxt) { int to = e[j].to; if(to==T||use[to>>1])continue; if(!e[j].w)continue; use[to>>1]=1; print(to>>1); break; } } int main() { scanf("%d",&n); memset(hed,-1,sizeof(hed)); S = 0,T = 1; for(m=1;;m++) { ae(S,m<<1,1);ae(m<<1,S,0); ae(m<<1|1,T,1);ae(T,m<<1|1,0); for(int i=1;i*i<2*m;i++) if(i*i>m)ae(m<<1,(i*i-m)<<1|1,1),ae((i*i-m)<<1|1,m<<1,0); if(!dinic())tot++; if(tot>n)break; } printf("%d ",m-1); for(int i=1;i<m;i++) { if(use[i])continue; use[i]=1; print(i); puts(""); } return 0; }