Cod sursa(job #2253644)

Utilizator Burbon13Burbon13 Burbon13 Data 4 octombrie 2018 11:09:49
Problema Cuplaj maxim in graf bipartit Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <vector>
#define NMAX 101

int n,m;
std::vector<int> gb[NMAX], gg[NMAX];
int rightPair[NMAX], leftPair[NMAX];

void initData() {
    for(int i = 0; i < NMAX; i++)
        rightPair[i] = leftPair[i] = -1;
}

void readInput() {
    int boys[NMAX], girls[NMAX];
    std::cin >> n;
    for(int i = 0; i < n; i++)
        std::cin >> boys[i];
    std::cin >> m;
    for(int i = 0; i < m; i++)
        std::cin >> girls[i];

    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(abs(boys[i]-girls[j]) <= 1) {
                gb[i].push_back(j);
                gg[j].push_back(i);
                std::cout << i << " -> " << j << '\n';
               // std::cout << j << " -> " << i << '\n';
            }
}

bool improve(const int&node) {
    for(const auto& next : gb[node])
        if(next != rightPair[node] && (leftPair[next] == -1 || improve(leftPair[next]))) {
            rightPair[node] = next;
            leftPair[next] = node;
            return true;
        }
    return false;
}

int coupleIt() {
    int total = 0;
    bool getBetter = true;
    while(getBetter) {
        getBetter = false;
        for(int i = 0; i < n; i++)
            if(rightPair[i] == -1 && improve(i)) {
                getBetter = true;
                total ++;
        }
    }
    return total;
}

int main() {
    initData();
    readInput();
    //std::cout << coupleIt() << '\n';
    return 0;
}