P6931 [ICPC2017 WF]Mission Improbable
题目链接：P6931
给定一个 r times c 的平面，在上面摆有一些箱子。我们可以得到他的三视图（如下图，左边矩阵上的值为平面上每一位摆放的箱子个数，右边三个视图为正视图，俯视图，左视图）：
你可以拿走一些箱子，和重新排列这些箱子的位置，你想知道，最多能拿走多少个箱子，使得这些箱子重新排列后正视图，俯视图，左视图不变？
比如上面这个例子，下面这种拿走 9 个箱子后的重新排列方式也是可以的：
1 le r,c le 100，平面上每一个位置的箱子个数在 [0,10^9] 内。
Tutorial
考虑俯视图限制显然是有数的则至少要有 1；主视图、侧视图限制即为每行每列的最大值仍然保留。
贪心地保留每行每列的一个最大值，其余的全削减至 1。
注意到可以有一个数同时占行列的最大值的情况。
于是跑一次二分图匹配即可。
Solution
代码语言：javascript复制#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 '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;
}
