0w1

CSAcademy 25. Zone Capture ( BCC )

Round #25 (Div. 2 only)

題意:
給一個 01 矩陣 A[ N ][ M ]。你可以選擇一個 0 轉為 1,轉換後,所有不和任意一個邊界的 0 屬於同一個連通塊 ( 上下左右,且兩者皆 0 視為相鄰 ) 的所有 0 都會轉為 1。問最多可以有多少 1。

制約:
1 ≤ N, M ≤ 1000

解法:
將所有格子化為節點編號,令 0 表示邊界, 將屬於邊界的 '0' 的節點連到 0。接著將所有相鄰的 '0' 也連一條邊。找出所有割點後,將 0 = 邊界 屬於的那塊 bcc 全部記為已拜訪。答案是原本的黑色格子數 + max( 1, 最大的剩餘連通塊大小 )。

時間 / 空間複雜度:
O( N * M )

#include <bits/stdc++.h>
using namespace std;

const int dx[] = { 1, 0, -1, 0 };
const int dy[] = { 0, 1, 0, -1 };

const int MAXN = 1000;
const int MAXM = 1000;

int N, M;
int mat[ MAXN ][ MAXM ];

vector< int > G[ MAXN * MAXM + 1 ]; // 0 preserved for "border"
int tin[ MAXN * MAXM + 1 ];
int low[ MAXN * MAXM + 1 ];
bool is_cut[ MAXN * MAXM + 1 ];

void dfs_bcc( int u, int fa ) {
  static int clk = 0;
  low[ u ] = tin[ u ] = ++clk;
  for( int v : G[ u ] ) {
    if( v == fa ) continue;
    if( not tin[ v ] ) {
      dfs_bcc( v, u );
      if( low[ v ] >= tin[ u ] and u != 0 ) {
        is_cut[ u ] = true;
      }
      low[ u ] = min( low[ u ], low[ v ] );
    }
    low[ u ] = min( low[ u ], tin[ v ] );
  }
}

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  int original_black = 0;
  for( int i = 0; i < N; ++i ) {
    for( int j = 0; j < M; ++j ) {
      cin >> mat[ i ][ j ];
      original_black += mat[ i ][ j ];
    }
  }
  for( int i = 0; i < N; ++i ) {
    for( int j = 0; j < M; ++j ) {
      if( mat[ i ][ j ] ) continue;
      if( i == 0 or i + 1 == N or j == 0 or j + 1 == M ) {
        G[ i * M + j + 1 ].emplace_back( 0 );
        G[ 0 ].emplace_back( i * M + j + 1 );
      }
      for( int di = 0; di < 4; ++di ) {
        int nx = i + dx[ di ];
        int ny = j + dy[ di ];
        if( not ( 0 <= nx and nx < N and 0 <= ny and ny < M ) ) continue;
        if( mat[ nx ][ ny ] ) continue;
        G[ i * M + j + 1 ].emplace_back( nx * M + ny + 1 );
        G[ nx * M + ny + 1 ].emplace_back( i * M + j + 1 );
      }
    }
  }
  dfs_bcc( 0, -1 );
  int max_cc_size = 0;
  {
    static bool vis[ MAXN * MAXM + 1 ];
    vis[ 0 ] = true;
    queue< int > que;
    que.emplace( 0 );
    while( not que.empty() ) {
      int u = que.front();
      que.pop();
      for( int v : G[ u ] ) {
        if( is_cut[ v ] ) continue;
        if( vis[ v ] ) continue;
        vis[ v ] = true;
        que.emplace( v );
      }
    }
    for( int i = 0; i < N; ++i ) {
      for( int j = 0; j < M; ++j ) {
        if( mat[ i ][ j ] ) continue;
        if( vis[ i * M + j + 1 ] ) continue;
        vis[ i * M + j + 1 ] = true;
        int cnt = 1;
        que.emplace( i * M + j + 1 );
        while( not que.empty() ) {
          int u = que.front();
          que.pop();
          for( int v : G[ u ] ) {
            if( vis[ v ] ) continue;
            vis[ v ] = true;
            ++cnt;
            que.emplace( v );
          }
        }
        max_cc_size = max( max_cc_size, cnt );
      }
    }
  }
  cout << original_black + max( 1, max_cc_size ) << endl;
  return 0;
}