1867번: 돌멩이 제거

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


$O(nk)$

(x,y)가 1일 떄 x->y 간선을 만들어 보면 이분 그래프를 만들 수 있으며 이 그래프에서 minimum vertex cover의 개수가 문제의 답이 된다.
이 수는 쾨닉의 정리에 따라 최대 이분 매칭 수와 같다.

#include<cstdio>
#include<vector>
using namespace std;
int n, k, p[501], vis[501], r;
vector<int> adj[501];
int dfs(int h) {
    if (!vis[h]) {
        vis[h] = 1;
        for (auto it : adj[h]) if (!p[it] || dfs(p[it])) {
            p[it] = h;
            return 1;
        }
    }
    return 0;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0, x, y; i < k; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) vis[j] = 0;
        r += dfs(i);
    }
    printf("%d", r);
    return 0;
}

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;
}