题解 | 算法竞赛进阶指南 Muddy Fields

思路

因为木板可以重叠,所以如果放置木板,木板两端肯定都顶到底(障碍或者边界)是最优的.
这样就可以预处理出一些横向与纵向的联通块(宽度都为1).因为每一个方格必须被覆盖,所以该方格隶属的横向联通块与纵向联通块至少有一个被木板覆盖.
这样就可以构建二分图,横向联通块为左部图,纵向联通块为右部图,每一个方格都是一条边,跑二分图最小点覆盖即可.

代码

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
#define go( i, b ) for ( int i(b), v(to[i]); i; v = to[i = nxt[i]] )
template<typename T> inline void cmax( T &x, T y ){ x < y ? x = y : x; }
template<typename T> inline void cmin( T &x, T y ){ y < x ? x = y : x; }

clock_t t_bg, t_ed;
const int MAXN = 55, MAXV = 2505, MAXE = 2505;
int N, M;
char s[MAXN][MAXN];
int b1[MAXN][MAXN], b2[MAXN][MAXN], n, m;
int hd[MAXV], nxt[MAXE], to[MAXE], tot;
int mc[MAXV]; bool vis[MAXV];
inline void addedge( int x, int y ){
    nxt[++tot] = hd[x], hd[x] = tot, to[tot] = y;
}

bool DFS( int u ){
    go( i, hd[u] ) if ( !vis[v] ){
        vis[v] = 1; if ( !mc[v] || DFS(mc[v]) ) return mc[v] = u, 1;
    } return 0;
}

int main(){
    t_bg = clock();
    scanf( "%d%d", &N, &M );
    fp( i, 1, N ) scanf( "%s", s[i] + 1 );
    fp( i, 1, N ) fp( j, 1, M ) if ( s[i][j] == '*' ){
        if ( s[i][j - 1] == '*' ) b1[i][j] = b1[i][j - 1];
        else b1[i][j] = ++n;
        if ( s[i - 1][j] == '*' ) b2[i][j] = b2[i - 1][j];
        else b2[i][j] = ++m;
        addedge( b1[i][j], b2[i][j] );
    } int ans(0); fp( i, 1, n ) memset( vis, 0, sizeof vis ), ans += DFS(i);
    printf( "%d\n", ans );
    t_ed = clock();
    fprintf( stderr, "\n========info========\ntime : %.3f\n====================\n", (double)( t_ed - t_bg ) / CLOCKS_PER_SEC );
    return 0;
}