[数据结构与算法]P2765 魔术球问题（网络流，隐式图构造）

P2765 魔术球问题

这道题的思路实在是太罕见了，所以发一篇blog

从某一新放入的球开始看起

1.放入原来的柱子上

2.放入新的柱子

并将每个点进行拆点，然后将可以组成平方数的两个树相连，在每次跑网络流的时候记录流的流向即可，如果流量为0，则表明1行不通，只能新来第一个柱子

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define inf 0x7fffffff
#define ll long long
//#define int long long
//#define double long double
#define re int
#define void inline void
#define eps 1e-5
//#define mod 1e9+7
#define ls(p) p<<1
#define rs(p) p<<1|1
//#define pi acos(-1.0)
#define pb push_back
#define P pair < int , int >
#define mk make_pair
#define fi first
#define se second
#define unordered_map map
//#define __int128 long long
using namespace std;
using namespace __gnu_pbds;
const int M=1e5+5;
const int mod=1e9;
const int N=2e6+5;
int n,s,t=100005;
int first[N],p,all;
int nxt[N],v[N];
namespace GP
{
	struct node
	{
		int ver,edge,next;
	}e[N];
	int tot=1,head[N];
	int d[N],gap[N];
	void add(int x,int y,int z)
	{
		e[++tot].ver=y;
		e[tot].edge=z;
		e[tot].next=head[x];
		head[x]=tot;
	}
	void addedge(int x,int y,int z)
	{
		add(x,y,z);add(y,x,0);
	}
	void bfs()
	{
		int z=rs(p);
//		printf("%d\n",rs(p));
		for(re i=0;i<=z;i++)  gap[i]=d[i]=0;
//		puts("sad");
		queue < int > q;
		q.push(t),d[t]=gap[1]=1;
//		cout<<"sdafd"<<endl;
		while(q.size())
		{
			int x=q.front();q.pop();
//			cout<<x<<endl;
			for(re i=head[x];i;i=e[i].next)
			{
				int y=e[i].ver;
				if(d[y])  continue;
				d[y]=d[x]+1;
				gap[d[y]]++;
				q.push(y);
			}
		}
	}
	int dfs(int x,int flow)
	{
		
		if(x==t)  return flow;
		int rest=0;
		for(re i=head[x];i;i=e[i].next)
		{
			int y=e[i].ver;
			int z=e[i].edge;
			if(!z||d[x]!=d[y]+1)  continue;
			int k=dfs(y,min(z,flow-rest));
			if(k<=0)  continue;
			e[i].edge-=k;
			e[i^1].edge+=k;
			rest+=k;
			nxt[x/2]=y/2;
			if(rest==flow)  return rest;
		}
		if(--gap[d[x]]==0)  d[s]=2*t+1;
		++gap[++d[x]];
		return rest;
	}
	int isap()
	{
		int maxflow=0;
		bfs();
		while(d[s]<=2*t)  maxflow+=dfs(s,1e9);
		return maxflow;
	}
}
void solve()
{
	cin>>n;
	while(all<=n)
	{
		p++;
		GP::addedge(s,ls(p),1);
		GP::addedge(rs(p),t,1);
//		cout<<s<<" | "<<p<<" | "<<ls(p)<<" | "<<t<<endl;
		for(re i=sqrt(p)+1;i*i<ls(p);i++)
		{
//			cout<<i*i-p<<endl;
			GP::addedge(ls(i*i-p),rs(p),1);
		}
//		puts("salj");
		int flow=GP::isap();
//		cout<<"flow: "<<flow<<endl;
		if(!flow)  first[++all]=p;
	}
	printf("%d\n",p-1);
	for(re x=1;x<=n;x++,puts(""))  if(!v[first[x]])
	{
		for(re i=first[x];i&&i!=(t/2);i=nxt[i])  printf("%d ",i);
	}
}
signed main()
{
//	fflush(stdout);
//	srand(102321547);
//	freopen("D.in", "r", stdin);
//	freopen("D2.out", "w", stdout);
//	freopen("9.out", "w", stdout);
    int T=1;
//    cin>>T;
    for(re index=1;index<=T;index++)
    {
//        printf("Case #%d:\n",index);
        solve();
//        puts("");
    }
    return 0;
}
/*


2
3 4 2 2
0000
0011
0000
1 4
2 4
3 4 2 2
0000
0011
0000
3 4
2 4


1
3 4 2 2
0000
1111
0000
1 4
2 4


2
3 4 2 2
0000
1111
0000
1 4
2 4
3 4 2 2
0000
0011
0000
3 4
2 4




*/