自动搬运

查看原文

来自洛谷，原作者为

	SGColin blog.gyx.me

搬运于2025-08-24 21:57:32，当前版本为作者最后更新于2019-03-30 11:37:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

把题面说清楚点:

给定一个大小为 $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;
}