Solution to BZOJ2406 矩阵。
赛时公告
现在呢？：现在有弹窗了吗 「2023-07-19 16:45:07」
此时无声胜有声。
F.「BZOJ2406」矩阵
http://222.180.160.110:61235/contest/3825/problem/7
这是头一次见识到把矩阵和网络流结合在一起的题目。不过这种处理方式也是我们在学习二分图时的常客了：把行和列连边表示某一元素。
我们发现 \(B_{i, j}\) 有给定的上下界，故我们考虑 上下界网络流。那怎么去表示 \(B_{i, j}\) 呢？这就要联系到我们刚刚说过的连边方式：用边 \(i\to j\) 的流量来表示 \(B_{i, j}\)，有 \([L, R]\) 的上下界。
可是我们除了 \([L,R]\) 的限制，还有最大值这个条件呀，怎么办呢？
注意到题目要求最大的最小，自然想到二分答案。设答案为 \(x\)，则我们需要保证每行每列的答案都 \(\le x\)。每行每列，这刚好是我们的建点方式。这对点本身作出了要求，这套路我们熟，让大源点向行连边、列向大汇点连边就好。
那么这些边的上下界怎么办呢？我们已知 \(|S_A-S_B|\le x\)，那么变形得：
\[ \begin{cases} S_B\ge S_A-x &(S_B \le S_A) \\ S_B\le S_A+x &(S_B \ge S_A) \end{cases} \]
照理来说，两行的符号相反，我们现在已经得到了一个具有对称美的上下界：\(S_A-x\le S_B\le S_A+x\)，就应该速速连边了，可是我怎么看都觉得不舒坦：这个不等式可是带条件的，就这么直接拿来做上下界真的没问题吗？
答案是没问题，因为我看的题解是这么写的
本着探索求真精神，我们考虑尊重原不等式（因为原不等式的每一行刚好也有两个相反的符号），将这些边拆成两条，一条的上下界是
\([S_A-x, S_A]\)，另一条是 \([S_A,S_A+x]\)。6。我明白题解为什么这么写了，一个的下界就是另一个的上界，那直接合并不就行了，这个
naive trick 题解都不屑于写出来。
然后跑个可行流就可以了。注意要保证边的下界为非负。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int lim = 2e5;
const int maxn = 405;
const int inf = 1e18;
const int maxm = 3e5 + 5;
struct _ {
int v, w, n;
_() {}
_(int v1, int w1, int n1) {
v = v1, w = w1, n = n1;
}
};
_ u[maxm];
int gs, gt, tot;
int a[maxn][maxn];
int l, mid, r, res;
int h[maxn], dif[maxn];
int n, m, cnt, s, t, L, R;
int vis[maxn], now[maxn], dep[maxn];
int max(int x, int y) { return x > y ? x : y; }
int min(int x, int y) { return x < y ? x : y; }
bool BFS(int n) {
std::fill(vis + 1, vis + n + 1, 0);
std::fill(dep + 1, dep + n + 1, 0);
std::queue<int> q;
dep[gs] = 1, vis[gs] = 1;
q.push(gs), now[gs] = h[gs];
while (!q.empty()) {
int f = q.front(); q.pop();
for (int i = h[f]; i; i = u[i].n) {
int v = u[i].v, w = u[i].w;
if (vis[v] == 1 || w == 0) continue;
vis[v] = 1, now[v] = h[v];
dep[v] = dep[f] + 1, q.push(v);
if (v == gt) return 1;
}
}
return 0;
}
int findP(int x, int flow = inf) {
if (x == gt) return flow;
int rest = flow, i;
for (i = now[x]; rest && i; i = u[i].n) {
now[x] = i;
int v = u[i].v, w = u[i].w;
if (dep[v] != dep[x] + 1 || w == 0) continue;
int t = findP(v, min(rest, w));
if (t == 0) dep[v] = 0;
rest -= t, u[i].w -= t, u[i ^ 1].w += t;
}
return flow - rest;
}
int Dinic(int n) {
int res = 0;
while (BFS(n)) {
int t = findP(gs);
while (t) res += t, t = findP(gs);
}
return res;
}
void add(int x, int y, int w) {
u[++tot] = _(y, w, h[x]), h[x] = tot;
return;
}
void add(int x, int y, int d, int u) {
add(x, y, u - d), add(y, x, 0);
dif[x] -= d, dif[y] += d;
return;
}
void Init(void) {
tot = 1, cnt = 0;
memset(h, 0, sizeof (h));
memset(dif, 0, sizeof (dif));
return;
}
bool check(int x) {
Init();
s = n + m + 1, t = s + 1;
add(t, s, inf), add(s, t, 0);
gs = t + 1, gt = t + 2;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j)
add(i, j + n, L, R);
}
for (int i = 1; i <= n; ++i) {
int sum = 0;
for (int j = 1; j <= m; ++j)
sum += a[i][j];
add(s, i, max(0, sum - x), sum + x);
}
for (int j = 1; j <= m; ++j) {
int sum = 0;
for (int i = 1; i <= n; ++i)
sum += a[i][j];
add(j + n, t, max(sum - x, 0), sum + x);
}
for (int i = 1; i <= t; ++i) {
if (dif[i] < 0)
add(i, gt, -dif[i]), add(gt, i, 0);
else if (dif[i] > 0) {
add(gs, i, dif[i]);
add(i, gs, 0), cnt += dif[i];
}
}
return (Dinic(gt) == cnt);
}
int main() {
read(n), read(m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j)
read(a[i][j]);
}
read(L), read(R);
l = 0, r = lim, res = -1;
while (l <= r) {
mid = (l + r) >> 1;
if (check(mid))
res = mid, r = mid - 1;
else l = mid + 1;
}
print(res);
return 0;
}
} // namespace XSC062
#undef int你最好有要事相求.jpg