洛谷 P2765 魔术球问题

传送门 $\looparrowright$

题目描述

假设有 $n$ 根柱子，现要按下述规则在这 $n$ 根柱子中依次放入编号为 $1,2,3\cdots$ 的球。
每次只能在某根柱子的最上面放球。同一根柱子中，任何 $2$ 个相邻球的编号之和为完全平方数。
试设计一个算法，计算出在 $n$ 根柱子上最多能放多少个球。例如，在 $4$ 根柱子上最多可放 $11$ 个球。
对于给定的 $n$ ，计算在 $n$ 根柱子上最多能放多少个球。

输入格式

只有一行一个整数 $n$ ，代表柱子数。

输出格式

本题存在 Special Judge。
请将 $n$ 根柱子上最多能放的球数以及相应的放置方案输出。
输出的第一行是球数。
接下来的 $n$ 行，每行若干个整数，代表一根柱子上的球的编号，数字间用单个空格隔开。

输入输出样例

输入 #1

4

输出 #1

11
1 8
2 7 9
3 6 10
4 5 11

说明/提示

对于 $100\%$ 的数据，保证 $1 \leqslant n \leqslant 55$ 。

分析

设当前有 $x$ 个球，将 $x$ 个球全部按要求放入柱子，需要的最少柱子数量为 $f(x)$ ， $f(x)=n$ 的最大解即为最多能放入的球的个数。显然， $f(x)$ 关于 $x$ 单调增加，不妨二分获得 $f(x)=n$ 的最大解。设二分的左边界为 $l$ ，边右界为 $r$ 。
接下来讨论，当有 $x$ 个球，编号为 $1\sim x$ ，最少需要多少根柱子使得 $x$ 个球全部按要求摆放在柱子上。
此问题虽然不是赤裸裸的图论问题，但是根据数字之间的关联和限制，就能在不同数字之间建边，转化为图论问题。
建边要遵循问题的要求和限制，若 $i+j$ 为完全平方数，且 $i<j$ ，那么就从 $i$ 向 $j$ 连边。这就遵循了将数字从小到大放入柱子且相邻数字和为完全平方数的原则。
当 $m=20$ 时，建立的 $\text{DAG}$ 如图。可以设想，最少需要的柱子数量为 $\text{DAG}$ 最小路径覆盖。（此图借用洛谷用户Rhodoks的博文）
借用洛谷博主的图https://www.luogu.com.cn/user/56267
二分得到一个解 $x$ ，对 $1\sim x$ 的所有整数建立上述的 $\text{DAG}$ ，并转化为拆点二分图，跑一次匈牙利算法即可得到最小路径覆盖。若最小路径覆盖仍然未超过 $n$ ，则左边界可继续增大，否则右边界减小。
获得最多能放入的球的个数的最大值 $m$ 后，再跑一次匈牙利算法，用 $\text{match}$ 数组输出匹配信息。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 洛谷 P2764
Date: 7/26/2020 
Description: Hungarian Alogrithm
*******************************************************************/
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N=10003;
const int base=5000;
const int M=15003;
struct E
{
	int to;
	int Next=-1;
}edge[M<<2];
int head[N<<2],tot;
int n,m;
bool vis[N<<2];
int match[N<<2];
inline void init();
inline void add_edge(int,int);
inline bool perfect_square(int);
bool dfs(int);
bool check(int);
int Hungarian(int);
void Hungarian();
int main()
{
	cin>>n;
	int i,j;
	int l=1,r=base;
	while(r-l>=3)//二分
	{
		int mid=l+r>>1;
		if(check(mid)) l=mid;
		else r=mid;
	}
	while(l<=r)
	{
		if(check(l)) 
		{
			m=l;
			l++;
		}
		else break;
	}
	cout<<m<<endl;
	init();
	//最后一次匈牙利输出匹配信息
	for(i=1;i<=m;i++)
	{
		for(j=i+1;j<=m;j++)
		{
			if(perfect_square(i+j))
			{
				add_edge(i,j+base);
			}
		}
	}
	Hungarian();
	return 0;
}
inline void init()
{
	memset(head,-1,sizeof(head));
	tot=0;
	memset(match,-1,sizeof(match));
}
inline void add_edge(int u,int v)
{
	tot++;
	edge[tot].to=v;
	edge[tot].Next=head[u];
	head[u]=tot;
}
inline bool perfect_square(int x) {return pow((int)sqrt(x),2)==x;}
bool dfs(int x)
{
	for(register int i=head[x];~i;i=edge[i].Next)
	{
		int y=edge[i].to;
		if(!vis[y])
		{
			vis[y]=1;
			if(match[y]==-1||dfs(match[y]))
			{
				match[y]=x;
				match[x]=y;
				return 1;
			}
		}
	}
	return 0;
}
bool check(int x)//球为x时的需要的最少柱子
{
	int i,j;
	init();
	//建立拆点二分图
	for(i=1;i<=x;i++)
	{
		for(j=i+1;j<=x;j++)
		{
			if(perfect_square(i+j))
			{
				add_edge(i,j+base);
			}
		}
	}
	return x-Hungarian(x)<=n;
}
int Hungarian(int x)
{
	int ans=0;
	for(register int i=1;i<=x;i++) 
	{
		memset(vis,0,sizeof(vis));
		ans+=dfs(i);
	}
	return ans;
}
void Hungarian()
{
	int temp=Hungarian(m);
	memset(vis,0,sizeof(vis));
	for(register int i=1;i<=m;i++)
	{
		if(!vis[i])
		{
			int x=base+i;
			do
			{
				x-=base;
				cout<<x<<' ';
				vis[x]=1;
				x=match[x];
			}while(~x);
			cout<<endl;
		}
	}
}