Cod sursa(job #1684238)

Utilizator bogdan2510Ionut Bogdan bogdan2510 Data 10 aprilie 2016 21:48:50
Problema Cuplaj maxim in graf bipartit Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define nmax 200005
using namespace std;
vector <bool> Use (nmax,false);
int L[nmax],R[nmax],GL[nmax],GR[nmax],n,m;
int cuplaj(int nod){
    if(Use[nod]) return 0;
    Use[nod]=true;
    for(int i=GL[nod];i>=1;i--){
        if(R[i]==0 && nod<=GR[i]){
            L[nod]=i;
            R[i]=nod;
            return 1;
        }
    }
    for(int i=GL[nod];i>=1;i--){
        if(nod<=GR[i])
            if(cuplaj(R[i])){
                L[nod]=i;
                R[i]=nod;
                return 1;
            }
    }
    return 0;
}
int main()
{
    freopen("cuplaje.in","r",stdin);
    freopen("cuplaje.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&GL[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d",&GR[i]);
    }
    bool ok=true;int contor=0;
    do{
        ok=false;
        Use=vector<bool> (nmax,false);
        for(int i=1;i<=n;i++){
            if(!L[i])
                if(cuplaj(i) ){
                    ok=true;
                    contor++;
                }
        }
    }while(ok);
    printf("%d",contor);
    return 0;
}