Cod sursa(job #1682844)

Utilizator bogdanboboc97Bogdan Boboc bogdanboboc97 Data 10 aprilie 2016 13:12:05
Problema Cuplaj maxim in graf bipartit Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int64 unsigned long long
#define INF numeric_limits<int64>::max()
#define lsb(x) (-x)&x
using namespace std;
ifstream in("cuplaje.in");
ofstream out("cuplaje.out");
vector< vector<int> > adj;
vector<int> gr1,gr2,fpref,bpref;
map< pair<int,int> , int > M;
vector<bool> v;
int n,m;
int pairup(int x)
{
    if(v[x])return 0;
    v[x]=true;
    for(auto it: adj[x])
        if(gr2[it]==0)
        {
            gr1[x]=it;
            gr2[it]=x;
            return 1;
        }
     for(auto it: adj[x])
        if(pairup(gr2[it])==1)
        {
            gr1[x]=it;
            gr2[it]=x;
            return 1;
        }
    return 0;
}
int main()
{
    in>>n>>m;
    adj=vector< vector<int> > (n+1);
    gr1=bpref=vector<int> (n+1);
    gr2=fpref=vector<int> (m+1);
    for(int i=1;i<=n;i++)
        in>>bpref[i];
    for(int i=1;i<=m;i++)
        in>>fpref[i];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=bpref[i];j++)
    if(fpref[j]>=i)
        adj[i].pb(j);
    for(int ok=1;ok!=0;)
    {
        ok=0;
        v=vector<bool>(n+1);
        for(int i=1;i<=n;i++)
            if(gr1[i]==0)
            ok+=pairup(i);
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
        if(gr1[i]!=0)
        cnt++;
    out<<cnt<<'\n';
    return 0;
}