自动搬运

查看原文

来自洛谷，原作者为

	CSPAK_Zhangxiuqi0011 愿，世上没有语文和数学！

搬运于2025-08-24 22:25:16，当前版本为作者最后更新于2025-08-06 14:01:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目简述

给定一个由边长为 $1$ 的正方体组成的立体图形，长，宽分别为 $r,c$。求最多取掉多少个小正方体，使得这个立体图形的三视图不变。

思路

题目中要我们取掉最多的小正方体，很容易转化成放最少的小正方体。
首先，我们考虑俯视图。
俯视图很简单，其实就是在之前有小正方体的地方放一个箱子。于是假设 $(i,j)$ 处原来有小正方体，则这个位置取走了 $a_{i,j}-1$ 个小正方体。这个我们在输入的时候就可以解决。
接下来考虑正视图和侧视图。
不难发现，每行/列的正/侧视图取决于这行/列中最高的那一个位置。那么，很容易想到，我们可以偷一点懒，假设这行/列最高的位置放了 $x$ 个小正方体，那么在这行/列只选一个位置放 $x$ 个小正方体不就行了吗？
于是，对于每一行/列，我们又放回去了 $x-1$ 个小正方体。需要注意的问题是：如果这一行这一列根本没有小正方体，那么直接跳过，否则会出错。
这道题就做完了吗？并没有。
很容易发现一种情况，举个例子说明：假如这个立体图形就是一个高度为 $4$ 的长方体呢？
按照刚才我们的做法，先取掉了 $3$ 个小正方体，然后第 $1$ 行和第 $1$ 列最高的都是 $4$，各放回去 $3$ 个小正方体，最后取走了 $-3$ 个小正方体。这个答案很明显是不对的。
那么，问题出在哪了呢？
很容易想到，当某一行和某一列的最高高度相等的时候（假设是 $y$），在这一行这一列的交点直接放 $y$ 个小正方体肯定比各在其他位置放 $y$ 个小正方体更优。于是遇到这种情况，直接在两列的交点放置即可，在上面基础上又少了 $y-1$ 个小正方体。
这道题做完了吗？还是没有。
我们再看一种情况：

3 3 3
3 3 3
3 3 3

按照刚才的做法，发现每行每列的最大高度都相同。于是，我们在每个交点处都放置 $3$ 个小正方体。放置之后的图和原图一样。
但是我们很容易发现，有一种方式是更优的：

3 1 1
1 3 1
1 1 3

也就是说，有些交点是根本没有必要放置的。
现在我们要解决的问题，就变成了：如何找到正确的交点？
观察上面的那个例子，可以发现，在我选了对角线三个点放 $3$ 个小正方体后，其他行/列都已经不用再放了。也就是说，每一行/列最好只有一个交点放小正方体。为什么是最好呢？很容易理解：

1 3 1
1 1 1
1 3 1

如图，很明显第 $1,3$ 行和第 $2$ 列最大值相等。我们在上面那个交点放了 $3$ 个小正方体后，虽然第 $2$ 列已经放好了，但是第 $3$ 行的高度 $3$ 只能放在第 $2$ 列。我们先把这个问题放在一边。
提到交点，可以想到二分图：
将每一行作为左部点，每一列作为右部点，如果某行和某列最大值相等，就把对应点连边。做二分图最大匹配，如果这一行匹配上了，令这一行的最大值为 $z$，则节省了 $z-1$ 个方块。
看到这里，我们会发现刚才上面丢下的问题也被解决了：在上面的例子中，第 $1$ 行和第 $2$ 列匹配上了，但是第 $3$ 行失配了，正好第 $2$ 列在上面放了一个 $3$，相当于第 $2$ 列放过了，第 $3$ 行只能老老实实放 $3$ 个方块，不能像上面的交点一样从原来的 $6$ 个方块节省到 $3$ 个方块（可以自己理解一下）。
那么有的同学就会问了（为啥会问）：每行匹配上的贡献不一定一样，为什么不用做带权最大匹配呢？
我们仔细想一想：我们刚才连边的条件是啥？是一行和一列最大值一样！所以若左部点（对应的行） $i$ 和 $j$ 最大值不同的时候，不管怎么匹配，都不会发生冲突（因为它们不可能联通）。如果最大值相同呢？那么不管哪个点匹配上了，只要数量相同，都是一样的。
这道题做完了吗？仍然没有。
我们再看一种情况：

5 0
0 3
3 0

可以发现，图中第 $3$ 行和第 $2$ 列最大值相等，直接在交点处放 $3$ 个小正方体更省事。但是原来第 $3$ 行第 $2$ 列这个位置并没有小正方体啊！如果放置了，则会导致俯视图改变，这里我们只能老老实实的在原本的位置放。所以，我们在连边之前一定要加一个判断条件：该行该列的交点处原本有小正方体（上面第 $1$ 行多加个 $5$ 是为了避免第 $2$ 行和第 $1$ 列最大值相等的情况，方便叙述，可以不看第一行）。
剩下的就是二分图板子啦！

Code

温馨提示：学习是给自己学的，请不要抄袭他人代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,a[105][105],x[105],y[105],vis[105],used[105];
vector<int>ve[105];
int find(int now){//匈牙利算法板子 
	int l;
	l = ve[now].size();
	for(int i = 0;i<l;i++){
		if(vis[ve[now][i]]){
			continue;
		}
		vis[ve[now][i]] = 1;
		if(!used[ve[now][i]] || find(used[ve[now][i]])){
			used[ve[now][i]] = now;
			return 1;
		}
	}
	return 0;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	int ans;
	ans = 0;
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]){
				ans = ans+a[i][j]-1;//处理俯视图情况（即只留1个小正方体） 
				x[i] = max(x[i],a[i][j]);
				y[j] = max(y[j],a[i][j]);//计算行和列最大值 
			}
		}
	}
	for(int i = 1;i<=n;i++){
		if(!x[i]){//如果这一行没有小正方体，直接跳过，要不然走到下面去的话ans值会减一 
			continue;
		}
		ans = ans-x[i]+1;
	}
	for(int i = 1;i<=m;i++){
		if(!y[i]){//同理 
			continue;
		}
		ans = ans-y[i]+1;
	}
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			if(x[i] == y[j] && a[i][j]){//一定要判断这个交点处是否有小正方体！ 
				ve[i].push_back(j);
			}
		}
	}
	for(int i = 1;i<=n;i++){
		memset(vis,0,sizeof(vis));
		if(find(i)){//是否能匹配上 
			ans = ans+x[i]-1;//在交点处放置，可以节省一些小正方体 
		}
	}
	cout<<ans<<"\n";
	return 0;
}