题目
点这里看题目。
分析
首先，不难发现此题可以方便地建出网络流的图来。图中的每个节点向周围四个点连一条容量为 1 的无向边，然后 (S) 连向红色接口， (T) 连向蓝色接口。
原题的答案便是此图上的最大流。显然原问题没法做，我们直接上最小割。
最小割本质上就是要将点拆分成两个点集。为了方便，我们就将 (S) 集合中的点染成红色， (T) 集合中的染成蓝色。
那么原图中的最小割就等于两端点颜色不同的边的数量。
考虑内部的 (n imes m) 个点应该如何最小化这种边的数量。仍然是为了方便，我们给异色端点的边上划一道垂直的虚线，考虑这样的虚线连为的路径。
如上图。假如电路板的内部出现了一个环，很显然我们应该改变内部点的颜色，消除它。这样答案不会变劣。
如上图。假如电路板内部出现了连接相邻的两个边界或者同一个边界的路径，我们显然应该改变它们的颜色，消除它们。这样答案不会变劣。
如上图。假如电路板内部出现了连接相对的两个边界的路径，我们同样可以改变它们的颜色，并且把它们拉直，使得它们在非边界的位置不拐弯。
因此，这样操作之后，图上就只会在列上或者行上存在连接相对边界的不拐弯的路径。
行列本身是类似的，单独考虑列。最终的最优情况就是所有列的颜色相同。
这个问题就可以用一个简单的 DP 来处理了：
(f(i,0/1))：前 (i) 行，颜色为 (0) （表示蓝色）或者 (1) (表示红色)时的最小割。
转移略。对行和列都做一遍，对所有的情况取 (min) 就是最小割，即答案。
关于 H2 ，由于 DP 的第二位很小，因此可以用矩阵来表示转移。这样就可以用线段树维护转移矩阵，单次修改是 (O(log_2n)) 的。
小结：
- 将问题建出对应的网络来，并且将最大流转换成最小割，将最小割转换成染色问题。
- 将染色问题转化为了类似于周长的问题，压缩最优解的情况。
代码
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 1e5 + 5;
template<typename _T>
void read( _T &x )
{
x = 0; char s = getchar(); int f = 1;
while( s < '0' || '9' < s ) { f = 1; if( s == '-' ) f = -1; s = getchar(); }
while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ); s = getchar(); }
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ) putchar( '-' ), x = -x;
if( 9 < x ) write( x / 10 );
putchar( x % 10 + '0' );
}
template<typename _T>
_T MIN( const _T a, const _T b )
{
return a < b ? a : b;
}
char S[MAXN];
int up[MAXN], down[MAXN], lef[MAXN], rig[MAXN];
int N, M, Q;
void Get( const int n, int *a )
{
scanf( "%s", S + 1 );
for( int i = 1 ; i <= n ; i ++ )
a[i] = S[i] == 'R';
}
int Calc()
{
int f0 = 0, f1 = 0, n0, n1;
for( int i = 1 ; i <= M ; i ++ ) f0 += up[i], f1 += ! up[i];
for( int i = 1 ; i <= N ; i ++ )
{
n0 = MIN( f0, f1 + M ) + lef[i] + rig[i];
n1 = MIN( f0 + M, f1 ) + ( ! lef[i] ) + ( ! rig[i] );
f0 = n0, f1 = n1;
}
for( int i = 1 ; i <= M ; i ++ ) f0 += down[i], f1 += ! down[i];
return MIN( f0, f1 );
}
int main()
{
read( N ), read( M ), read( Q );
Get( N, lef ), Get( N, rig );
Get( M, up ), Get( M, down );
int ans1 = Calc(), ans2;
swap( N, M ), swap( up, lef ), swap( down, rig );
ans2 = Calc();
write( MIN( ans1, ans2 ) ), putchar( '
' );
return 0;
}