5307. 【NOIP2017提高A组模拟8.18】偷窃 (Standard IO)

Time Limits: 1000 ms Memory Limits: 262144 KB

Description

Input

Output

Sample Input

5 5

1 4 0 5 2

2 1 2 0 1

0 2 3 4 4

0 3 0 3 1

1 2 2 1 1

Sample Output

Data Constraint

Hint

题解

乍一看以为是贪心，贪心保留最大的

后来，发现有个诡异的地方

这是一个会搬砖的小偷

于是，只能用二分图了

如果第i行和第j列最大值相等且可以放，就连一条边

跑一遍匹配匹配到的边就只算一次，代表只放一个就能满足一行和一列

匹配不到的行和列，就分别算一次

代码

#include<cstdio>

#include<cstring>

#include<vector>

#define N 101

using namespace std;

vector<long>map[N];

long a[N][N],link[N],hang[N],lie[N];

bool cover[N];

bool find(long now)

{   long i,to;

    for(i=0;i<map[now].size();i++){

        to=map[now][i];

        if(!cover[to]){

            cover[to]=true;

            if(!link[to]||find(link[to])){

                link[to]=now;

                return true;

            }

        }

    }

    return false;

}

int main()

{   long n,m,i,j,ans=0,sum=0;

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

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

        for(j=1;j<=m;j++){

            scanf("%ld",&a[i][j]);

            hang[i]=max(hang[i],a[i][j]);

            lie[j]=max(lie[j],a[i][j]);

            if(a[i][j])

                sum+=a[i][j]-1;

        }

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

        if(hang[i])ans+=hang[i]-1;

    for(j=1;j<=m;j++)

        if(lie[j])ans+=lie[j]-1;

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

        for(j=1;j<=m;j++){

            if(hang[i]==lie[j]&&a[i][j])

                map[i].push_back(j);

        }

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

        memset(cover,false,sizeof(cover));

        if(find(i))

            ans-=hang[i]-1;

    }

    printf("%ld\n",sum-ans);

    return 0;

}

巴特西

JZOJ 5307. 【NOIP2017提高A组模拟8.18】偷窃 (Standard IO)