CSES - School Dance | Vũ hội trường - LQDOJ: Le Quy Don Online Judge

CSES - School Dance | Vũ hội trường

Tác giả:

Flower_On_Stone , nhphucqt , NguyễnAnhQuốc_83

Dạng bài

Điểm: 2000 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Có \(n\) nam sinh và \(m\) nữ sinh trong một trường học. Tuần tới, một buổi khiêu vũ của trường sẽ được tổ chức. Một cặp nhảy bao gồm một nam sinh và một nữ sinh, và có \(k\) cặp tiềm năng.

Nhiệm vụ của bạn là tìm ra số lượng cặp nhảy tối đa và chỉ ra cách đạt được con số này.

Input

Dòng đầu tiên là ba số nguyên \(n, m\) và \(k\): số nam sinh, nữ sinh và các cặp tiềm năng. Các nam sinh được đánh số \(1,2,\ldots, n\) và các nữ sinh được đánh số \(1,2,\ldots, m\).
\(k\) dòng tiếp theo mô tả các cặp tiềm năng. Mỗi dòng gồm hai số nguyên \(a\) và \(b\): nam sinh a và nữ sinh b sẵn sàng nhảy cùng nhau.

Output

Đầu tiên in một số nguyên \(r\): số lượng cặp nhảy tối đa. Sau đó, in \(r\) dòng mô tả các cặp. Bạn có thể in bất kỳ giải pháp hợp lệ nào.

Constraints

\(1 \le n, m \le 500\)
\(1 \le k \le 1000\)
\(1 \le a \le n\)
\(1 \le b \le m\)

Example

Test 1

Input

Output

2
1 2
3 1

Bình luận

Hint

Python

def max(n, m, k, cap):
    g = [[] for _ in range(n + 1)]
    for a, b in cap:
        g[a].append(b)
    noi = [-1] * (m + 1)

    def thunoi(v, vv):
        for u in g[v]:
            if not vv[u]:
                vv[u] = True
                if noi[u] == -1 or thunoi(noi[u], vv):
                    noi[u] = v
                    return True
        return False

    kq = []
    for v in range(1, n + 1):
        vv = [False] * (m + 1)
        if thunoi(v, vv):
            for u in range(1, m + 1):
                if noi[u] == v:
                    kq.append((v, u))
    print(len(kq))
    for a, b in kq:
        print(a, b)
n, m, k = map(int, input().split())
cap = [tuple(map(int, input().split())) for _ in range(k)]
max(n, m, k, cap)

C++

#include <iostream>
#include <vector>
using namespace std;

void max_matching(int n, int m, int k, const vector<pair<int, int>>& cap) {
    vector<vector<int>> g(n + 1);
    for (const auto& p : cap) {
        g[p.first].push_back(p.second);
    }

    vector<int> noi(m + 1, -1);

    auto thunoi = [&](int v, vector<bool>& vv, auto& thunoi_ref) -> bool {
        for (int u : g[v]) {
            if (!vv[u]) {
                vv[u] = true;
                if (noi[u] == -1 || thunoi_ref(noi[u], vv, thunoi_ref)) {
                    noi[u] = v;
                    return true;
                }
            }
        }
        return false;
    };

    vector<pair<int, int>> kq;
    for (int v = 1; v <= n; ++v) {
        vector<bool> vv(m + 1, false);
        if (thunoi(v, vv, thunoi)) {
            for (int u = 1; u <= m; ++u) {
                if (noi[u] == v) {
                    kq.emplace_back(v, u);
                }
            }
        }
    }

    cout << kq.size() << endl;
    for (const auto& p : kq) {
        cout << p.first << " " << p.second << endl;
    }
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<pair<int, int>> cap(k);
    for (int i = 0; i < k; ++i) {
        cin >> cap[i].first >> cap[i].second;
    }

    max_matching(n, m, k, cap);
    return 0;
}

1 bình luận nữa