\(\mathcal{Description}\)

给定一个 \(n\times m\) 的矩阵 \(A\)，构造一个 \(n\times m\) 的矩阵 \(B\)，s.t. \((\forall i\in[1,n],j\in[1,m])(b_{ij}\in[L,R])\)，且最小化：

\[\max\left\{\max_{i=1}^n\{\left|\sum_{j=1}^m a_{ij}-b_{ij}\right|,\max_{j=1}^m\left| \sum_{i=1}^n a_{ij}-b_{ij} \right|\right\}
\]

输出上式最小值即可。

\(n,m\le200\)，\(0\le 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\n", 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\n", l );

	return 0;

}

巴特西

Solution -「洛谷 P4194」矩阵

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章