Cod sursa(job #2430483)

Utilizator freak93Adrian Budau freak93 Data 15 iunie 2019 00:37:43
Problema Cuplaj maxim in graf bipartit Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cassert>
#include <cstring>
#include <cstdio>

using namespace std;

int m_used[10005];
int m_left[10005];
int m_right[10005];
vector<int> m_edges[10006];

bool go(int node) {
    m_used[node] = true;

    for (auto &next : m_edges[node])
        if (m_right[next] == -1 || (!m_used[m_right[next]] && go(m_right[next]))) {
            m_left[node] = next;
            m_right[next] = node;
            return true;
        }
    return false;
}

int main() {
    freopen("cuplaj.in", "r", stdin);
    freopen("cuplaj.out", "w", stdout);

    ios::sync_with_stdio(false);

    //ifstream cin("cuplaj.in");
    //ofstream cout("cuplaj.out");

    int N, M, E; cin >> N >> M >> E;
    for (int i = 0; i < E; ++i) {
        int x, y; cin >> x >> y;
        m_edges[x - 1].emplace_back(y - 1);
    }

    memset(m_left, -1, sizeof(m_left));
    memset(m_right, -1, sizeof(m_right));

    //for (auto &edges : m_edges)
    //    random_shuffle(edges.begin(), edges.end());

    while (true) {
        memset(m_used, 0, sizeof(m_used));
        bool try_again = false;
        for (int i = 0; i < N; ++i)
            if (!m_used[i] && m_left[i] == -1)
                try_again = (try_again || go(i));
        if (!try_again)
            break;
    }

    vector< pair<int, int> > match;
    for (int i = 0; i < N; ++i)
        if (m_left[i] != -1)
            match.emplace_back(i, m_left[i]);

    cout << match.size() << "\n";
    for (auto &p : match)
        cout << p.first + 1 << " " << p.second + 1 << "\n";
}