P2765 魔术球问题

题目描述

问题描述：

假设有\(n\)根柱子，现要按下述规则在这\(n\)根柱子中依次放入编号为\(1,2,3,\dots\)的球。

\((1)\) 每次只能在某根柱子的最上面放球。

\((2)\) 在同一根柱子中，任何\(2\)个相邻球的编号之和为完全平方数。

试设计一个算法，计算出在\(n\)根柱子上最多能放多少个球。例如，在 \(4\) 根柱子上最多可放 \(11\) 个球。

编程任务：

对于给定的\(n\)，计算在\(n\)根柱子上最多能放多少个球。

输入输出格式

输入格式：

第\(1\)行有\(1\)个正整数\(n\)，表示柱子数。

输出格式：

程序运行结束时，将 \(n\) 根柱子上最多能放的球数以及相应的放置方案输出。

文件的第一行是球数。

接下来的\(n\)行，每行是一根柱子上的球的编号。

说明

感谢 @PhoenixEclipse 提供spj

\(4\le n\le 55\)

---

首先可以发现柱子越多球不会放的更少，所以可以二分答案球的个数。

把球向大的数值连有向边，发现是对DAG求最小路径覆盖，那么直接二分图匹配求。

求匹配也可以跑网络流，不过就不能二分了，每次加球在残余网络上跑，看看跑不跑的出新流量，跑不出来就加柱子。

二分上界可以最开始二分一下，发现不超过2000

---

Code:

#include <cstdio>

#include <cstring>

#include <cmath>

const int N=2010;

const int M=2e5+10;

int head[N],to[M],Next[M],cnt;

void add(int u,int v)

{

	to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;

}

int k,match[N],vis[N],bee[N];

bool dfs(int now)

{

	for(int v,i=head[now];i;i=Next[i])

	{

		if(!vis[v=to[i]])

		{

			vis[v]=1;

			if(!match[v]||dfs(match[v]))

				return bee[match[v]=now]=v,true;

		}

	}

	return false;

}

bool check(int n)

{

	memset(head,0,sizeof head),cnt=0;

	memset(match,0,sizeof match);

	memset(bee,0,sizeof bee);

	int ans=0;

	for(int i=1;i<=n;i++)

		for(int j=sqrt(i<<1)+1;j*j-i<=n;j++)

			if(j*j-i>i) add(i,j*j-i);

	for(int i=1;i<=n;i++)

	{

		memset(vis,0,sizeof vis);

		if(dfs(i)) ++ans;

	}

	return n-ans<=k;

}

void dfs0(int now)

{

	if(vis[now]) return;

	vis[now]=1;

	printf("%d ",now);

	dfs0(bee[now]);

}

int main()

{

	scanf("%d",&k);

	int l=1,r=2000;

	while(l<r)

	{

		int mid=l+r+1>>1;

		if(check(mid)) l=mid;

		else r=mid-1;

	}

	check(l);

	printf("%d\n",l);

	memset(vis,0,sizeof vis),vis[0]=1;

	for(int i=1;i<=l;i++)

		if(!vis[i])

			dfs0(i),puts("");

	return 0;

}

---

2019.1.16