Algorithm in A..Z - Maximum Independent Set

개념

그래프 G에서 정접들의 집합을 S라고 할 때 S의 부분 집합 'S를 골랐을 때 서로 인접하지 않으면 독립 집합이라 하고 이중에서 'S의 크기가 가장 큰 독립집합을 최대 독립집합이라고 한다.

 

Maximum Independent Set의 특징은 Maximum Independent Set의 여집합은 Minimum Vertex Cover이다.

=> 최대 집합 - Minimum Vertex Cover = 최대 독립 집합

=> 최대 집합 - 최대 이분 매칭 = 최대 독립 집합이다

---

시간복잡도

이분매칭 할 때 : O(V^(1/2) * E)

---

문제

11014 컨닝2

www.acmicpc.net/problem/11014

11014번: 컨닝 2

---

코드

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

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

int nn = 0;
vector<int> point;
vector<vector<int>> graph;

vector<bool> isMatched;
vector<int> depth, isChecked;

void bfs() {
    queue<int> que;
    for (int i = 0;i < nn;++i) {
        if (!isMatched[i]) {
            que.emplace(i);
            depth[i] = 0;
        } else {
            depth[i] = INT32_MAX;
        }
    }

    while (!que.empty()) {
        auto now = que.front();que.pop();

        for (auto &next : graph[now]) {
            if (isChecked[next] != -1 && depth[isChecked[next]] == INT32_MAX) {
                depth[isChecked[next]] = depth[now] + 1;
                que.emplace(isChecked[next]);
            }
        }
    }
}

bool dfs(int index) {
    for (auto &next : graph[index]) {
        if (isChecked[next] == -1 || (depth[index] + 1 == depth[isChecked[next]] && dfs(isChecked[next]))) {
            isChecked[next] = index;
            isMatched[index] = true;
            return true;
        }
    }

    return false;
}

int binmatch() {
    isMatched.assign(nn, false);
    depth.resize(nn);
    isChecked.assign(nn, - 1);

    int result = 0;
    while (true) {
        bfs();

        int flow = 0;
        for (int i : point) {
            if (!isMatched[i]) {
                flow += dfs(i);
            }
        }

        if (flow == 0) {
            break;
        } else {
            result += flow;
        }
    }

    return result;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        point.clear();
        graph.clear();

        int n, m;
        cin >> n >> m;

        vector<string> map(n);
        for (auto &str : map) {
            cin >> str;
        }

        vector<vector<int>> number(n, vector<int>(m));

        nn = 0;
        int crash = 0;
        for (int i = 0;i < n;++i) {
            for (int j = 0;j < m;++j) {
                if (map[i][j] == 'x') {
                    crash++;
                    continue;
                }

                if (j % 2) {
                    point.emplace_back(nn);
                }

                number[i][j] = nn++;
            }
        }

        graph.resize(nn);
        for (int i = 0;i < n;++i) {
            for (int j = 0;j < m;++j) {
                if (map[i][j] == 'x') {
                    continue;
                }

                for (int k = 0;k < 6;++k) {
                    int xx = j + dx[k];
                    int yy = i + dy[k];

                    if (xx < 0 || yy < 0 || xx >= m || yy >= n || map[yy][xx] == 'x') {
                        continue;
                    }

                    graph[number[i][j]].emplace_back(number[yy][xx]);
                }
            }
        }

        cout << n*m - binmatch() - crash << "\n";
    }
}