2051번: 최소 버텍스 커버

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

$O(n^2m)$

#include<cstdio>
#include<vector>
using namespace std;
int n, m, r[1001], vis[1001], res, ck[1001], acnt, bcnt, b[1001];
vector<int> adj[1001];
int f(int h) {
    if (vis[h]) return 0;
    vis[h] = 1;
    for (int it : adj[h]) {
        if (!r[it] || f(r[it])) {
            r[it] = h;
            return 1;
        }
    }
    return 0;
}
void g(int h) {
    if (vis[h]) return;
    vis[h] = 1;
    acnt++;
    for (int it : adj[h]) bcnt += !b[it]++, g(r[it]);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, x, y; i <= n; i++)
        for (scanf("%d", &x); x--;) scanf("%d", &y), adj[i].push_back(y);
    for (int i = 1; i <= n; i++) {
        if (f(i)) ck[i] = 1, res++;
        for (int j = 1; j <= n; j++) vis[j] = 0;
    }
    for (int i = 1; i <= n; i++) if (!ck[i]) g(i);
    printf("%d\n%d", res, n - acnt);
    for (int i = 1; i <= n; i++) if (!vis[i]) printf(" %d", i);
    printf("\n%d", bcnt);
    for (int i = 1; i <= n; i++) if (b[i]) printf(" %d", i);
    return 0;
}

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