[ICPC2017 WF]C – Mission Improbable

题目链接: https://codeforces.com/gym/101471

Solution

观察一下,想要保持俯视图不变,只需要让没有数字的仍然没有数字,有数字的仍然有数字(数字 \geq1 )即可。

对于主视图,让每列最大的数,仍然是那一列最大的数就满足。

对于侧视图,让每行最大的数,仍然是那一行最大的数就满足。

那么显然,最优的情况是,一个数,既是那一列最大的数,也是那一行最大的数。

比如

100 20
 20 10

最优的情况是

100  1
  1 20

通俗地讲就是,我们要维持这一行的最大值 A 不变,就要把这个最大值 A 放在这一行的某一列上。(对于列也一样)

那么这一行的每一列都可以放这个数,但是如果有一列的最大值 B 等于这一行的最大值 A ,那么我们把这个数放在这一行的这一列上,既满足了这一行的要求,也满足了那一列的要求(就不用再为那一列的 B 去另找一个位置了)

那么这一个数所放的位置 (x,y) 既满足了 x 行 ,又满足了 y 列,这种情况肯定是最优的情况。

那么我们要为某一行找另一列,就要用到二分图最大匹配了。

代码如下:

#include
using namespace std;
const int N = 105;
int s[N][N],n,m;
int r[N],c[N],tim;
int v[N],F[N];
vector vec[N<<1];
long long ans=0;
bool find(int x){
    for(auto p:vec[x]){
        if(v[p]==tim) continue;
        v[p]=tim;
        if(!F[p]||find(F[p])){
            F[p]=x;
            return 1;
        }   
    }
    return 0;
}
int main(){

    scanf("%d %d",&n,&m);

    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            scanf("%d",&s[i][j]);
            if(s[i][j]) 
                ans+=1ll*s[i][j]-1;
            r[i]=max(r[i],s[i][j]);
            c[j]=max(c[j],s[i][j]);
        }
    }

    for(int i=1;i<=n;++i) if(r[i]) ans-=1ll*r[i]-1;
    for(int i=1;i<=m;++i) if(c[i]) ans-=1ll*c[i]-1;

    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(r[i]==c[j]&&s[i][j])
                vec[i].push_back(j);
        }
    }

    for(int i=1;i<=n;++i){
        if(!r[i]) continue;
        ++tim;
        if(find(i)) ans+=1ll*r[i]-1;
    }
    printf("%lld",ans);
    return 0;
}
分类: 思维

0 条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注