P6931 [ICPC2017 WF]Mission Improbable

(Updated: )
oi
,

题目链接：P6931

给定一个 $r \times c$ 的平面，在上面摆有一些箱子。我们可以得到他的三视图（如下图，左边矩阵上的值为平面上每一位摆放的箱子个数，右边三个视图为正视图，俯视图，左视图）：

你可以拿走一些箱子，和重新排列这些箱子的位置，你想知道，最多能拿走多少个箱子，使得这些箱子重新排列后正视图，俯视图，左视图不变？

比如上面这个例子，下面这种拿走 $9$ 个箱子后的重新排列方式也是可以的：

$1 \le r,c \le 100$，平面上每一个位置的箱子个数在 $[0,10^9]$ 内。

Tutorial

考虑俯视图限制显然是有数的则至少要有 $1$；主视图、侧视图限制即为每行每列的最大值仍然保留。

贪心地保留每行每列的一个最大值，其余的全削减至 $1$。

注意到可以有一个数同时占行列的最大值的情况。

于是跑一次二分图匹配即可。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
	Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
	Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
	Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
	Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
	Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=110,P=N<<1;
int n,m,a[N][N],r[N],c[N],fir[P],nxt[P*P*2],son[P*P*2],w[P*P*2],cost[P*P*2],p[P],tot=1,S,T,F[P],G[P],inf,vis[P];LL Ans;
I void Add(CI x,CI y,CI z,CI c){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y,w[tot]=z,cost[tot]=c;nxt[++tot]=fir[y],fir[y]=tot,son[tot]=x,w[tot]=0,cost[tot]=-c;}
#define to son[i]
I int idx(CI i,CI j){return (i-1)*m+j;}
queue<int> q;
I bool BFS(){
	RI i,u;memset(F,63,sizeof(F)),memset(vis,0,sizeof(vis)),inf=F[0];W(!q.empty()) q.pop();q.push(S),vis[S]=1,F[S]=0,G[S]=inf;W(!q.empty())
		for(vis[u=q.front()]=0,q.pop(),i=fir[u];i;i=nxt[i]) w[i]&&F[to]>F[u]+cost[i]&&(F[to]=F[u]+cost[i],G[to]=min(G[u],w[p[to]=i]),!vis[to]&&(q.push(to),vis[to]=1));
	return F[T]<inf;
}
I LL MCMF(){LL i,X=0,C=0;W(BFS()) for(C+=1LL*F[T]*G[T],X+=G[i=T];i^S;i=son[p[i]^1]) w[p[i]]-=G[T],w[p[i]^1]+=G[T];return C;}
int main(){
	RI i,j;for(read(n,m),S=0,T=n+m+1,i=1;i<=n;i++) for(j=1;j<=m;j++) read(a[i][j]),r[i]=max(r[i],a[i][j]),c[j]=max(c[j],a[i][j]);
	for(i=1;i<=n;i++) Ans-=max(r[i]-1,0);for(i=1;i<=m;i++) Ans-=max(c[i]-1,0);
	for(i=1;i<=n;i++) for(j=1;j<=m;j++) Ans+=max(a[i][j]-1,0),r[i]==c[j]&&a[i][j]&&(Add(i,j+n,1,max(r[i]-1,0)),0);
	for(i=1;i<=n;i++) Add(S,i,1,0);for(i=1;i<=m;i++) Add(i+n,T,1,0);
	return writeln(Ans+MCMF()),0;
}