hckim

문제링크

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

풀이

• 구조의 가치는 구조를 이루는 간선의 수이다.
• 링 또는 선형으로만 구성되어있다는 것은 한 정점에서 나가는 간선, 들어오는 간선은 최대 1개씩 있을 수 있다는 뜻
• 간선의 시작점, 도착점 두 그룹으로 이분매칭

코드

• 시간복잡도: $O(VE) = O(NM)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int TC; cin >> TC;
    while (TC--) {
        int N, M;
        cin >> N >> M;

        vector<vector<int> > adj(N);
        vector<int> B(N, -1);

        for (int i = 0; i < M; ++i) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
        }
        vector<int> visited(N, 0);
        function<bool(int)> f = [&](int a) {
            visited[a] = true;
            for (auto b: adj[a]) {
                if (B[b] == -1 || (!visited[B[b]] && f(B[b]))) {
                    B[b] = a;
                    return true;
                }
            }
            return false;
        };

        long long ans = 0;
        for (int i = 0; i < N; ++i) {
            fill(all(visited), false);
            ans += f(i);
        }
        cout << ans << '\n';
    }
}

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

풀이1. Maximum flow(에드몬드 카프)

최대 K 명까지 일을 두개 할 수 있다는 것을 Source 에서 용량 K 로 이어진 추가 노드를 구성함으로써 구현

코드1.

• 단방향 플로우에서 역방향 간선의 capacity = 0 으로 해야함에 주의
• 시간복잡도: $min(O((V + E)f), O(VE^2)) \to O((V + E)(V + K))$ 

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
struct Edge {
    int to, c, f;
    Edge* reverse;

    Edge() {
        to = 0;
        c = 0;
        f = 0;
        reverse = nullptr;
    }
    int residual() {
        return c - f;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, K;
    cin >> N >> M >> K;
    vector<vector<Edge*> > adj(N + M + 3);
    auto makeEdge = [&](int n1, int n2, int cc) {
        auto e1 = new Edge();
        auto e2 = new Edge();

        e1 -> to = n2;
        e1 -> reverse = e2;
        e1 -> c = cc;
        e2 -> to = n1;
        e2 -> reverse = e1;

        adj[n1].push_back(e1);
        adj[n2].push_back(e2);
    };

    int S = 0, T = N + M + 1, X = N + M + 2;

    makeEdge(S, X, K);
    for (int i = 1; i <= N; ++i) {
        int num;
        cin >> num;
        makeEdge(S, i, 1);
        makeEdge(X, i, 1);
        while (num--) {
            int w;
            cin >> w;
            makeEdge(i, N + w, 1);
        }
    }
    for (int i = 1; i <= M; ++i) {
        makeEdge(N + i, T, 1);
    }

    while (true) {
        vector<Edge*> prev(N + M + 3, nullptr);
        queue<int> q;
        q.push(S);
        while (!q.empty()) {
            auto f = q.front();
            q.pop();

            for (auto e: adj[f]) {
                if (e -> residual() <= 0) continue;
                if (prev[e -> to]) continue;
                q.push(e -> to);
                prev[e -> to] = e;
                if (e -> to == T) break;
            }
            if (prev[T]) break;
        }

        if (!prev[T]) break;

        int flow = 1e9;
        for (auto cur = T; cur != S; cur = prev[cur] -> reverse -> to) {
            flow = min(flow, prev[cur] -> residual());
        }
        for (auto cur = T; cur != S; cur = prev[cur] -> reverse -> to) {
            prev[cur] -> f += flow;
            prev[cur] -> reverse -> f -= flow;
        }
    }

    int answer = 0;
    for (auto e: adj[T]) {
        answer += e -> reverse -> f;
    }
    cout << answer << '\n';
}

풀이2. Bipartite matching

직원당 두개의 노드를 만들고 그룹 두개로 나눠서 한그룹에서 이분매칭 후 두번째 그룹에서 K번 이하 이분매칭

코드2. 

• 시간복잡도: $O(VE)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, K;
    cin >> N >> M >> K;

    vector<int> A(2 * N + 1, 0), B(M + 1, 0);
    vector<vector<int> > adj(2 * N + 1);

    for (int i = 1; i <= N; ++i) {
        int num;
        cin >> num;
        while (num--) {
            int m;
            cin >> m;
            adj[2 * i - 1].push_back(m);
            adj[2 * i].push_back(m);
        }
    }

    vector<int> visited(2 * N + 1, false);
    function<bool(int)> f = [&](int a) {
        visited[a] = true;
        for (auto b: adj[a]) {
            if (!B[b] || (!visited[B[b]] && f(B[b]))) {
                A[a] = b;
                B[b] = a;
                return true;
            }            
        }
        return false;
    };

    int match = 0;
    for (int i = 1; i <= 2 * N; i += 2) {
        if (!A[i]) {
            fill(all(visited), false);
            if (f(i)) ++match;
        }
    }
    int matched2 = 0;
    for (int i = 2; i <= 2 * N && matched2 < K; i += 2) {
        if (!A[i]) {
            fill(all(visited), false);
            if (f(i)) ++matched2;
        }
    }

    cout << match + matched2 << '\n';
}