题解：P6931 [ICPC 2017 WF] Mission Improbable

· · 题解

题目简述

给定一个由边长为 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;
}