2414번: 게시판 구멍 막기

https://www.acmicpc.net/problem/2414


$O(n^2m^2)$

가로, 세로로 연속적으로 구멍뚤린 부분을 하나의 노드로 보고 같은 지점을 공유하는 노드끼리 이어주면 이분 그래프를 만들 수 있다.
이 그래프에서 minimum vertex cover가 곧 문제의 정답이고 이는 Kőnig's theorem에 따라 최대 매칭을 구하는 문제와 동치이다.

#include<cstdio>
#include<vector>
using namespace std;
int r[50][50], c[50][50], rcnt, ccnt, n, m, vis[2500], p[2500], flow, t;
char s[50][51];
vector<int> adj[2500];
int f(int h) {
    if (vis[h] == t) return 0;
    vis[h] = t;
    for (auto it : adj[h]) if (p[it] == -1 || f(p[it])) {
        p[it] = h;
        return 1;
    }
    return 0;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%s", s[i]);
        for (int j = 0; j < m; j++) if (s[i][j] == '*') {
            r[i][j] = !j || s[i][j - 1] == '.' ? rcnt++ : r[i][j - 1];
            c[i][j] = !i || s[i - 1][j] == '.' ? ccnt++ : c[i - 1][j];
            adj[r[i][j]].push_back(c[i][j]);
        }
    }
    for (int i = 0; i < ccnt; i++) p[i] = -1;
    for (int i = 0; i < rcnt; i++) ++t, flow += f(i);
    printf("%d", flow);
    return 0;
}