「网络流24题」魔术球问题

发表于 | 分类于 | | 浏览量： 次

纳尼？这是网络流？？？

传送门

洛谷P2765

LOJ6003

题解

这题一眼看上去就是一个贪心。

从小到大枚举球的编号，然后从$1$到$n$枚举柱子，找到第一个可以放上去的柱子后就把球放上去，直到放不了位置。

这个贪心看起来很假，但是是对的。

考虑网络流的做法，对于两个球，如果编号加和为完全平方数，那么就从编号小的球往编号大的球建一条边。然后整张图的最小路径覆盖就等于所需柱子的数量。从小到大枚举球的个数，当所需柱子的数量大于$n​$时就上一次的个数就是答案。

考虑贪心和网络流的关系。

其实贪心的过程就是往网络里加点的过程。由于优先考虑加到有球的柱子上，所以就相当于在维护最小路径覆盖是的数量。

所以贪心的做法本质上和网络流的做法是一样的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<cmath>
#include<cstdio>
using namespace std;
const int maxn=60;
int n,ans,top[maxn],A[maxn][maxn];
inline bool check(int x)
{
	int sq=sqrt(x)+1e-10;
	return sq*sq==x;
}
int main()
{
	scanf("%d",&n);
	while(true)
	{
		bool suc=false;
		for(int i=1;i<=n;i++)
			if(top[i]==0||check(A[i][top[i]]+ans+1))
				{ans++;top[i]++;A[i][top[i]]=ans;suc=true;break;}
		if(!suc) break;
	}
	printf("%d\n",ans);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=top[i];j++)
			printf("%d%c",A[i][j],j==top[i]?'\n':' ');
	return 0;
}