BOJ)1444 숌 언어

문제:icpc.me/1444

대문자와 소문자가 번갈아 나타나는 문장이 주어질 때 대문자와 소문자로 이루어진 최소 몇개의 단어로 문장을 만들 수 있는지를 출력하는 문제이다.

이 문제는 (대문자,소문자)로 이루어진 단어와 (소문자,대문자)로 이루어진 단어의 이분 그래프로 나타내면 최소 버텍스 커버 문제로 치환하여 해결할 수 있다.

예를들어 AaAbBa라는 단어가 있을 때

Ab라는 정점과 bB라는 정점이 연결되고 bB라는 정점과 Ba라는 정점이 연결될 것이다.

이 연결을 할 수 있게 만드는 정점의 최소수를 구하는 문제이기 때문에 최소 버텍스 커버 문제로 해결 가능한 것이다.

하지만 맨 처음 나오는 Aa라는 단어와 Ba라는 단어는 항상 선택이 강제 되어야하므로 해당 단어와 연결 된 간선들을 모두 제거해준 뒤 그 두단어는 버텍스 커버에 항상 선택된다고 생각한 뒤 문제를 해결하면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
char a[3030];
int n, b[2 * 26 * 26 + 1], visited[2 * 26 * 26 + 1], s, e, r;
vector<int> vt[2 * 26 * 26 + 1];
int cvt(char a, char b) {
    if ('A' <= a&&a <= 'Z') {
        int x = a - 'A';
        int y = b - 'a';
        return x * 26 + y + 1;
    }
    else {
        int x = a - 'a';
        int y = b - 'A';
        return x * 26 + y + 26 * 26 + 1;
    }
}
int dfs(int here) {
    if (visited[here])return 0;
    visited[here] = 1;
    for (auto next : vt[here]) {
        if (!b[next] || dfs(b[next])) {
            b[next] = here;
            return 1;
        }
    }
    return 0;
}
int bmatch() {
    int ret = 0;
    for (int i = 1; i <= 26 * 26; i++) {
        memset(visited, 0, sizeof(visited));
        if (dfs(i))ret++;
    }
    return ret;
}
int main() {
    scanf("%s", &a);
    for (n; a[n]; n++) {}
    s = cvt(a[0], a[1]);
    e = cvt(a[n - 2], a[n - 1]);
    r += s == e ? 1 : 2;
    for (int i = 1; i < n - 1; i ++) {
        int x = cvt(a[i - 1], a[i]);
        int y = cvt(a[i], a[i + 1]);
        if (s != x&&s != y&&e != x&&e != y) {
            vt[x].push_back(y);
            vt[y].push_back(x);
        }
    }
    r += bmatch();
    printf("%d\n", r);
    return 0;
}