P4194 矩阵 题解
link
一道比较版的费用流练手题。
看见这个最大的最小，考虑二分答案。
则对于每一行，任务转化为判断 \(|\sum_{j=1}^mA_{i,j}-B_{i,j}|\leqslant mid\)，即 \(|\sum_{j=1}^mA_{i,j}-\sum_{j=1}^mB_{i,j}|\leqslant mid\)。发现这个 sigma 不好调配，那么用这个常见的 trick：将整个行/整个列看成一个点。那么直接行列搞成二分图，中间连边表示每个点，再用上下界网络流（有源汇可行流判断即可）。
具体地，\(1\sim n\) 表示行，\(n+1\sim n+m\) 表示列。我们先将初始源点与 \(1\sim n\) 连，边权为 \([row_i-mid,row_i+mid]\)，同理 \(n+1\sim n+m\) 与 \([column_j-mid,column_j+mid]\) 连。然后对于 \(i\) 与 \(n+j\) 连边 \([L,R]\)。跑可行流。
#include
#include
#include
#include
#include
#include
#define Min(x,y) ((x)<(y)?(x):(y))
#define LL long long
using namespace std;
const int MAXN = 405, MAXM = 205 * 205 * 2 + 205 * 6, inf = 0x3f3f3f3f;
struct Node {
int X, Y, Z;
}edge[MAXM];
int n, m, d[MAXN], S, T, que[MAXN], head, tail, cur[MAXN], D[MAXN], Dow, Up;
int Head[MAXN], Next[MAXM], res[MAXM], tot = 1, s_, t_, a[MAXN][MAXN], line[MAXN], row[MAXN];
void Add(int x, int y, int z) {
tot ++; edge[tot].X = x; edge[tot].Y = y; edge[tot].Z = z; Next[tot] = Head[x]; Head[x] = tot;
}
void addedge(int x, int y, int z) {
Add(x, y, z); Add(y, x, 0);
}
int dfs(int x, int las) {
if(x == T || !las) return las;
int all = 0;
for(int &i = cur[x]; i; i = Next[i]) {
if(d[edge[i].Y] + 1 == d[x] && edge[i].Z) {
int t = dfs(edge[i].Y, Min(las - all, edge[i].Z));
if(!t) d[edge[i].Y] = -233;
all += t; edge[i].Z -= t; edge[i ^ 1].Z += t;
if(all == las) return all;
}
}
return all;
}
bool bfs(bool lim) {
for(int i = 0; i <= T; i ++) d[i] = 0;
head = 1; tail = 0; que[++ tail] = T; d[T] = 1;
while(head <= tail) {
int t = que[head ++];
for(int i = Head[t]; i; i = Next[i]) {
if((!d[edge[i].Y] && edge[i ^ 1].Z) && (lim || (i & 1))) {
d[edge[i].Y] = d[t] + 1; que[++ tail] = edge[i].Y;
if(edge[i].Y == S) return 1;
}
}
}
return (d[S] > 0);
}
int Dinic() {
int ans = 0, t = 0;
while(bfs(0)) {
for(int i = 0; i <= T; i ++) cur[i] = Head[i]; // S~T
while(t = dfs(S, inf)) ans += t;
}
while(bfs(1)) {
for(int i = 0; i <= T; i ++) cur[i] = Head[i];
while(t = dfs(S, inf)) ans += t;
}
return ans;
}
// 你 m的网络流. 网络流害人不浅.
bool Check(int mid) {
int avg = 0;
s_ = n + m + 1; t_ = n + m + 2; S = n + m + 3; T = n + m + 4; tot = 1;
for(int i = 0; i <= T; i ++) Head[i] = 0, D[i] = 0;
for(int i = 1; i <= n; i ++) {
D[s_] += line[i] - mid; D[i] -= line[i] - mid;
addedge(s_, i, 2 * mid); // [line[i]-mid, line[i]+mid]
}
for(int i = 1; i <= m; i ++) {
// [L,R]
D[i + n] += row[i] - mid; D[t_] -= row[i] - mid;
addedge(i + n, t_, 2 * mid);
}
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) {
// [L,R]
D[i] += Dow; D[n + j] -= Dow;
addedge(i, n + j, Up - Dow);
}
}
for(int i = 0; i <= t_; i ++) {
if(D[i] > 0) addedge(i, T, D[i]), avg += D[i];
else if(D[i] < 0) addedge(S, i, -D[i]);
}
addedge(t_, s_, inf);
int ans = Dinic();
return (ans == avg);
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) scanf("%d", &a[i][j]), line[i] += a[i][j], row[j] += a[i][j];
int l = 0, r = 1000 * 200, mid, res = 0;
scanf("%d%d", &Dow, &Up);
while(l <= r) {
mid = (l + r) >> 1;
if(Check(mid)) r = mid - 1, res = mid;
else l = mid + 1;
}
printf("%d", res);
return 0;
}