题解：P6931 [ICPC 2017 WF] Mission Improbable

#include<bits/stdc++.h>
#define il inline
#define vd void
using namespace std;
typedef long long ll;
il int gi() {
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-')f = -1;
		ch = getchar();
	}
	while (isdigit(ch))x = x * 10 + ch - '0', ch = getchar();
	return x * f;
}
ll A[101][101], H[101], W[101];
int S, T, fir[210], dis[30010], nxt[30010], w[30010], id = 1;
ll cost[30010];
il vd link(int a, int b, ll d) {
	nxt[++id] = fir[a], fir[a] = id, dis[id] = b, w[id] = 1, cost[id] = d;
	nxt[++id] = fir[b], fir[b] = id, dis[id] = a, w[id] = 0, cost[id] = -d;
}
il bool Mincost(ll&total) {
	static ll dist[210];
	static int que[210], hd, tl, lst[210];
	static bool inq[210];
	memset(dist, 63, sizeof dist);
	dist[S] = 0;
	hd = tl = 0;
	que[tl++] = S;
	inq[S] = 1;
	lst[T] = 0;
	while (hd ^ tl) {
		int x = que[hd];
		for (int i = fir[x]; i; i = nxt[i])
			if (w[i] && dist[dis[i]] > dist[x] + cost[i]) {
				dist[dis[i]] = dist[x] + cost[i], lst[dis[i]] = i;
				if (!inq[dis[i]])inq[dis[i]] = 1, que[tl++] = dis[i], tl %= 210;
			}
		inq[x] = 0, ++hd, hd %= 210;
	}
	for (int i = lst[T]; i; i = lst[dis[i ^ 1]])w[i] = 0, w[i ^ 1] = 1, total -= cost[i];
	return lst[T];
}
int main() {
	int n = gi(), m = gi();
	ll ans = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			A[i][j] = gi();
			if (A[i][j])ans += A[i][j] - 1;
			H[i] = std::max(H[i], A[i][j]);
			W[j] = std::max(W[j], A[i][j]);
		}
	for (int i = 1; i <= n; ++i)if (H[i])ans -= H[i] - 1;
	for (int i = 1; i <= m; ++i)if (W[i])ans -= W[i] - 1;
	S = 0, T = n + m + 1;
	for (int i = 1; i <= n; ++i)link(S, i, 0);
	for (int i = 1; i <= m; ++i)link(i + n, T, 0);
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			if (A[i][j] && H[i] == W[j] && H[i])link(i, n + j, -H[i] + 1);
	while (Mincost(ans));
	printf("%lld\n", ans);
	return 0;
}