「网络流 24 题」魔术球
solution:
我们考虑枚举最多能放多少球,那么对于每个新加的球有两种方法
- 重新安排一个柱子让它放
- 放在某个和它组成平方数的球的后面
于是我们将这个球拆成两个点u和_u
将源点s连向u容量为1,表示重新安排一个柱子
将_u连向汇点t容量为1,对于和它能构成平方数的v,连接v到_u容量为1
表示它可以放到和它组成平方数的球的后面
然后就跑最大流就行了
code:
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=2e5+5;
int n,tot=1,s,t;
int fi[N],ne[M],to[M],c[M],d[N],pre[N],head[N];
inline void add(int x,int y,int s){ne[++tot]=fi[x],fi[x]=tot,to[tot]=y,c[tot]=s;}
inline void ad(int x,int y,int s){add(x,y,s),add(y,x,0);}
inline bool bfs()
{
memset(d,-1,sizeof(d));d[s]=0;
queue<int>q;q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=fi[u];i;i=ne[i])
if(c[i]&&d[to[i]]==-1)
{
d[to[i]]=d[u]+1;
q.push(to[i]);
}
}
return d[t]!=-1;
}
int dfs(int u,int flow)
{
if(u==t||!flow)return flow;
int used=0;
for(int i=fi[u];i;i=ne[i])
{
int v=to[i];
if(!c[i]||d[v]!=d[u]+1)continue;
int f=dfs(v,min(flow-used,c[i]));
if(!f)continue;
c[i]-=f,c[i^1]+=f;used+=f;
pre[u>>1]=v>>1;
if(used==flow)break;
}
if(used<flow)d[u]=-1;
return used;
}
inline int dinic()
{
int e=0;
while(bfs())e+=dfs(s,1e9);
return e;
}
int main()
{
scanf("%d",&n);
int cnt=0,now=0;
s=1,t=10000;
while(cnt<=n)
{
++now;
ad(s,now<<1,1),ad(now<<1|1,t,1);
for(int i=ceil(sqrt(now+0.5));i*i<now*2;++i)
ad((i*i-now)<<1,now<<1|1,1);
int f=dinic();
if(!f)head[++cnt]=now;
}
printf("%d\n",now-1);
for(int i=1;i<=n;++i,puts(""))
for(int j=head[i];j<now&&j;j=pre[j])
printf("%d%s",j,pre[j]<now&&pre[j]?" ":"");
return 0;
}