BZOJ2406 矩阵 <上下界网络流>

Problem

矩阵

Time Limit: $10 Sec$
Memory Limit: $128 MB$

Description

![][1]

Input

第一行两个数$n$、$m$，表示矩阵的大小。
接下来$n$行，每行$m$列，描述矩阵$A$。
最后一行两个数$L$，$R$。

Output

一行，输出最小的答案。

Sample Input

2 2
0 1
2 1
0 1

Sample Output

1

HINT

$N,M\le 200$, $0\le L\le R\le 1000$, $0\le A_{i,j}\le 1000$

标签：线性规划，上下界网络流

Solution

线性规划转上下界网络流。
看到所求为最大值中的最小，可想到二分答案。
对于当前答案$tans​$，验证是否能构造矩阵B使得：

• 对于$\forall i\in [1,n],\ \forall j\in[1,m]$，$L\le B_{i,j}\le R$
• 对于$\forall i \in [1,n]$，$\sum_{j=1}^{m}{A_{i,j}}-tans \le \sum_{j=1}^{m}{B_{i,j}} \le \sum_{j=1}^{m}{A_{i,j}}+tans$
• 对于$\forall j\in [1,m]$，$\sum_{i=1}^{n}{A_{i,j}}-tans \le \sum_{i=1}^{n}{B_{i,j}} \le \sum_{i=1}^{n}{A_{i,j}}+tans$
  而$n,m$又只有200，不难想到跑网络流验证。

将每行每列设为点（共$n+m$个），建图:

• $S\to row_i$ 容量$[\sum_{j=1}^{m}{A_{i,j}}-tans,\ \ \sum_{j=1}^{m}{A_{i,j}}+tans]$
• $column_j \to T$ 容量$[\sum_{i=1}^{n}{A_{i,j}}-tans, \ \ \sum_{i=1}^{n}{A_{i,j}}+tans]$
• $row_i\to column_j$ 容量$[L,\ \ R]$

赫然是个上下界网络流。
建虚拟源虚拟汇跑最大流看是否等于补流即可。
建图，$SS,TT$为上下界网络流的原源和原汇，$S,T$为虚拟源和汇，$d[]$记录补流：

• $TT\to SS$ 容量$\infty$
• $row_i\to column_j​$ 容量$R-L​$，$d[row_i] +L,\ \ d[column_j] - L​$
• $SS\to row_i$ 容量$\sum_{j=1}^{m}{A_{i,j}}-tans$，$d[SS]+2\times tans,\ \ d[row_i]-2\times tans$
• $column_j \to TT$ 容量$\sum_{i=1}^{n}{A_{i,j}}-tans$，$d[column_j]+2\times tans,\ \ d[TT]-2\times tans$

随后将此图和虚拟源汇接上：
对于$x\in \{row_{1\sim n}\}\cup \{column_{1\sim m}\}\cup \{SS,TT\}$

• 若$d[x] < 0$，连接$S\to x$ 容量$-d[x]$，$tot_补-d[x]$
• 若$d[x] > 0$，连接$x \to T$ 容量$d[x]$，$tot_分+d[x]$

最后判断$tot_补=tot_分=MaxFlow$

Code

#include <bits/stdc++.h>
#define MAX_N 500000
#define MAX_M 500000
#define INF 0x3f3f3f3f
#define mid ((p+q)>>1)
using namespace std;
template <class T>
inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int r, c, x[205], y[205], P, Q;
int n, s, t, ss, tt, cnt, d[MAX_N+5], pr[MAX_N+5], cr[MAX_N+5];
struct node {int v, c, nxt;} E[MAX_M+5];
void init() {cnt = 0, s = 0, t = r+c+1, ss = t+1, tt = t+2, memset(pr, -1, sizeof pr), memset(d, 0, sizeof d);}
void insert(int u, int v, int c) {E[cnt] = (node){v, c, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c) {insert(u, v, c), insert(v, u, 0);}
bool BFS() {
    queue <int> que;	que.push(s);
    memset(d, -1, sizeof d), d[s] = 0;
    while (!que.empty()) {
        int u = que.front();	que.pop();
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;
            if (~d[v] || !c) continue;
            d[v] = d[u]+1, que.push(v);
        }
    }
    return ~d[t];
}
int DFS(int u, int flow) {
    if (u == t) return flow;	int ret = 0;
    for (int i = pr[u]; ~i; i = E[i].nxt) {
        int v = E[i].v, c = E[i].c;
        if (d[u]+1 != d[v] || !c) continue;
        int tmp = DFS(v, min(flow, c));
        E[i].c -= tmp, E[i^1].c += tmp;
        flow -= tmp, ret += tmp;
        if (!flow) break;
    }
    if (!ret) d[u] = -1;	return ret;
}
int Dinic() {int ret = 0;    while (BFS()) ret += DFS(s, INF);	return ret;}
bool check(int tans) {
    int into = 0, outo = 0;	init(), n = r+c+2, addedge(tt, ss, INF);
    for (int i = 1; i <= r; i++) for (int j = 1; j <= c; j++)
        addedge(i, j+r, Q-P), d[i] += P, d[j+r] -= P;
    for (int i = 1; i <= r; i++) addedge(ss, i, 2*tans), d[ss] += x[i]-tans, d[i] -= x[i]-tans;
    for (int i = 1; i <= c; i++) addedge(i+r, tt, 2*tans), d[i+r] += y[i]-tans, d[tt] -= y[i]-tans;
    for (int i = 1; i <= tt; i++) if (i^t) {
        if (d[i] < 0) addedge(s, i, -d[i]), into -= d[i];
        if (d[i] > 0) addedge(i, t, d[i]), outo += d[i];
    }
    return into == outo && Dinic() == into;
}
int bi_search(int p, int q) {int ret = -1; while (p <= q) if (check(mid)) ret = mid, q = mid-1; else p = mid+1; return ret;}
int main() {
    read(r), read(c);
    for (int i = 1; i <= r; i++) for (int j = 1, val; j <= c; j++)
        read(val), x[i] += val, y[j] += val;
    return read(P), read(Q), printf("%d", bi_search(0, 200000)), 0;
}