P6931 [ICPC2017 WF]Mission Improbable

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