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
9
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;
}