(mathcal{Description})
Link.
给定一个 (n imes m) 的矩阵 (A)，构造一个 (n imes m) 的矩阵 (B)，s.t. ((forall iin[1,n],jin[1,m])(b_{ij}in[L,R]))，且最小化：
[maxleft{max_{i=1}^n{left|sum_{j=1}^m a_{ij}-b_{ij}
ight|,max_{j=1}^mleft| sum_{i=1}^n a_{ij}-b_{ij}
ight|
ight}
]
输出上式最小值即可。
(n,mle200)，(0le L,R,a_{ij}le10^3)。
(mathcal{Solution})
不难想到二分答案。记 (r_i=sum_{j=1}^m a_{ij})，(c_i=sum_{j=1}^n a_{ji})，设当前答案为 (x)，则第 (i) 行的取值区间为 ([max{0,r_i-x},r_i+x])，第 (i) 列的取值区间为 ([max{0,c_i-x},c_i+x])，然后 (B) 的每个元素又有限制 ([L,R])，所以猜测可以通过求上下界可行流来构造 (B)：
- (S) 连向 (n) 个行虚点 (r_1,r_2,cdots,r_n)，流量区间如上；
- 行虚点 (r_i) 连向第 (i) 行元素入点 (bi_{ij})，流量无限制；
- 元素入点 (bi_{ij}) 连向元素出点 (bo_{ij})，流量区间 ([L,R])；
- 元素出点 (bo_{ij}) 连向列虚点 (c_j)，流量无限制；
- (m) 个列虚点 (c_1,c_2,cdots,c_m) 连向 (T)，流量区间如上。
求这个有源汇流网络是否存在可行流即可判断 (x) 是否合法。
复杂度 (mathcal O(log(nR)D))，其中 (D) 为这种分层图下 Dinic 算法的复杂度。
(mathcal{Code})
/* Clearink */
#include <queue>
#include <cstdio>
const int MAXN = 300, MAXV = 1e3, MAXND = MAXN * ( MAXN + 1 ) * 2 + 2, INF = 0x3f3f3f3f;
int n, m, L, R, rsum[MAXN + 5], csum[MAXN + 5], deg[MAXND + 5];
inline int imin ( const int a, const int b ) { return a < b ? a : b; }
inline int imax ( const int a, const int b ) { return a < b ? b : a; }
struct MaxFlowGraph {
static const int MAXND = ::MAXND + 2, MAXEG = MAXN * MAXN * 3 + MAXN * 2;
int ecnt, head[MAXND + 5], S, T, bound, curh[MAXND + 5], d[MAXND + 5];
struct Edge { int to, flow, nxt; } graph[MAXEG * 2 + 5];
inline void clear () {
ecnt = 1;
for ( int i = 0; i <= bound; ++i ) head[i] = 0;
}
inline void link ( const int s, const int t, const int f ) {
graph[++ecnt] = { t, f, head[s] };
head[s] = ecnt;
}
inline Edge& operator [] ( const int k ) { return graph[k]; }
inline void operator () ( const int s, const int t, const int f ) {
#ifdef RYBY
printf ( "%d %d ", s, t );
if ( f == INF ) puts ( "INF" );
else printf ( "%d
", f );
#endif
link ( s, t, f ), link ( t, s, 0 );
}
inline bool bfs () {
static std::queue<int> que;
for ( int i = 0; i <= bound; ++i ) d[i] = -1;
d[S] = 0, que.push ( S );
while ( !que.empty () ) {
int u = que.front (); que.pop ();
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( graph[i].flow && !~d[v = graph[i].to] ) {
d[v] = d[u] + 1;
que.push ( v );
}
}
}
return ~d[T];
}
inline int dfs ( const int u, const int iflow ) {
if ( u == T ) return iflow;
int ret = 0;
for ( int& i = curh[u], v; i; i = graph[i].nxt ) {
if ( graph[i].flow && d[v = graph[i].to] == d[u] + 1 ) {
int oflow = dfs ( v, imin ( iflow - ret, graph[i].flow ) );
ret += oflow, graph[i].flow -= oflow, graph[i ^ 1].flow += oflow;
if ( ret == iflow ) break;
}
}
if ( !ret ) d[u] = -1;
return ret;
}
inline int calc ( const int s, const int t ) {
S = s, T = t;
int ret = 0;
for ( ; bfs (); ret += dfs ( S, INF ) ) {
for ( int i = 0; i <= bound; ++i ) curh[i] = head[i];
}
return ret;
}
} graph;
inline bool check ( const int lim ) {
int cnt = n * m * 2;
graph.bound = cnt + n + m + 3;
graph.clear (), graph.S = cnt + n + m + 2, graph.T = graph.S + 1;
int rS = 0, rT = cnt + n + m + 1;
for ( int i = 0; i <= graph.bound; ++i ) deg[i] = 0;
for ( int i = 1; i <= n; ++i ) { // row.
int lw = imax ( 0, rsum[i] - lim ), up = rsum[i] + lim;
deg[rS] -= lw, deg[cnt + i] += lw;
graph ( rS, cnt + i, up - lw );
}
for ( int i = 1; i <= m; ++i ) { // col.
int lw = imax ( 0, csum[i] - lim ), up = csum[i] + lim;
deg[cnt + n + i] -= lw, deg[rT] += lw;
graph ( cnt + n + i, rT, up - lw );
}
for ( int i = 1; i <= n; ++i ) {
for ( int j = 1; j <= m; ++j ) {
int id = ( i - 1 ) * m + j, rid = id + n * m;
deg[id] -= L, deg[rid] += L;
graph ( id, rid, R - L );
graph ( cnt + i, id, INF ), graph ( rid, cnt + n + j, INF );
}
}
int req = 0;
for ( int i = rS; i <= rT; ++i ) {
if ( deg[i] > 0 ) graph ( graph.S, i, deg[i] );
else if ( deg[i] ) req -= deg[i], graph ( i, graph.T, -deg[i] );
}
graph ( rT, rS, INF );
return graph.calc ( graph.S, graph.T ) == req;
}
int main () {
scanf ( "%d %d", &n, &m );
for ( int i = 1; i <= n; ++i ) {
for ( int j = 1, a; j <= m; ++j ) {
scanf ( "%d", &a );
rsum[i] += a, csum[j] += a;
}
}
scanf ( "%d %d", &L, &R );
int l = 0, r = imax ( n, m ) * R;
while ( l < r ) {
int mid = l + r >> 1;
if ( check ( mid ) ) r = mid;
else l = mid + 1;
}
printf ( "%d
", l );
return 0;
}