题解 P4194 【矩阵】

· · 题解

把题面说清楚点:

给定一个大小为 n\times m 的矩阵 A，让你求一个大小相同的矩阵 B，要求 B_{i,j}\in[L,R]，设矩阵 C 为 C_{i,j}=A_{i,j}-B_{i,j}，最小化 C 每一行的和的绝对值，以及每一列的和的绝对值的最大值。

设 sumh_i 表示 \sum_{j=1}^m A_{i,j}，设 suml_i 表示 \sum_{j=1}^n A_{j,i} 。

考虑二分答案，那么也就是要求 |\sum A_{i,j}-\sum B_{i,j}|\le mid 。

将绝对值分情况讨论，得到 \sum B_{i,j} 的范围是 [\sum A_{i,j}-mid,\sum A_{i,j}+mid]，也就是说每一行 B 的和需要是 [-mid,mid]+sumh_i，列也同理。

考虑用有源汇有上下界可行流验证，将每一行，和每一列单独开一个点。 S 向每一行连 [sumh_i-mid,sumh_i + mid] 的边，每一列向 T 连 [suml_i-mid,suml_i + mid] 的边，对应的每一行和每一列连 [L,R] 的边。

如果存在可行流，那么我们构造的 B 矩阵就是： B_{i,j} 为第 i 行抽象出来的点向第 j 列抽象出来的点最后的流量，显然单点的要求和行列的要求都会被满足。

关于二分的合法性，显然是差越大越容易构造。从另一个角度去想，最后重建图的上下界网络流其实边的容量就是 2mid，显然 2mid 越大越容易找到解。

#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 405
#define M 100005
#define inf 2000000000
using namespace std;

inline int rd() {
  int x = 0;
  char c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) {
    x = x * 10 + (c ^ 48); c = getchar();
  }
  return x;
}

int n, m, s, t, S, T, tot, hd[N], dlt[N];

struct E{int to, nxt, f, mnf;} e[M << 1];

inline void add(int u, int v, int f) {
  e[++tot].to = v; e[tot].f = f; e[tot].nxt = hd[u]; hd[u] = tot;
  e[++tot].to = u; e[tot].f = 0; e[tot].nxt = hd[v]; hd[v] = tot;
}

inline void adde(int u, int v, int mnf, int mxf) {
  add(u, v, mxf - mnf);
  e[tot - 1].mnf = mnf;
  dlt[v] += mnf; dlt[u] -= mnf;
}

struct Q {
  int a[N << 1], hd, tl;
  inline void pop() {++hd;}
  inline int front() {return a[hd];}
  inline void reset() {hd = 1; tl = 0;}
  inline void push(int x) {a[++tl] = x;}
  inline bool empty() {return hd > tl;}
} q;

int d[N], h[N];

inline bool bfs() {
  memset(d, 0, sizeof(d));
  q.reset(); q.push(S); d[S] = 1;
  while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int i = hd[u], v; i; i = e[i].nxt)
      if (!d[v = e[i].to] && e[i].f) {
        d[v] = d[u] + 1; q.push(v);
      }
  }
  return d[T] > 0;
}

int dfs(int u, int flow) {
  if (u == T || !flow) return flow;
  int res = 0, tmp;
  for (int &i = h[u], v; i; i = e[i].nxt)
    if (d[v = e[i].to] == d[u] + 1 && e[i].f) {
      tmp = dfs(v, min(e[i].f, flow - res));
      if (!tmp) {d[v] = -1; continue;}
      res += tmp; e[i].f -= tmp; e[i ^ 1].f += tmp;
      if (res == flow) return res;
    }
  return res;
}

inline int dinic() {
  int totf = 0;
  while (bfs()) {
    memcpy(h, hd, sizeof(hd));
    totf += dfs(S, inf);
  }
  return totf;
}

int L, R, a[N][N], sumh[N], suml[N];

inline bool valid(int mid) {
  tot = 1;
  memset(hd, 0, sizeof(hd));
  memset(dlt, 0, sizeof(dlt));
  int sum = 0;
  s = 0; t = n + m + 1;
  for (int i = 1; i <= n; ++i) {
    adde(s, i, sumh[i] - mid, sumh[i] + mid);
    for (int j = 1; j <= m; ++j) adde(i, j + n, L, R);
  }
  for (int i = 1; i <= m; ++i)
    adde(i + n, t, suml[i] - mid, suml[i] + mid);
  add(t, s, inf);
  S = N - 2; T = N - 1;
  for (int i = s; i <= t; ++i)
    if (dlt[i] > 0) {
      add(S, i, dlt[i]); sum += dlt[i];
    }
    else if (dlt[i] < 0) add(i, T, -dlt[i]);
  return dinic() == sum;
}

int main() {
  n = rd(); m = rd();
  for (int i = 1; i <= n; ++i)
    for (int j = 1, x; j <= m; ++j) {
      x = rd(); sumh[i] += x; suml[j] += x;
    }
  L = rd(); R = rd();
  int l = 0, r = 400000, mid;
  while (l < r) {
    mid = (l + r) >> 1;
    valid(mid) ? r = mid : l = mid + 1;
  }
  printf("%d\n", l);
  return 0;
}