Cod sursa(job #2614796)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 12 mai 2020 18:12:33
Problema Cuplaj maxim in graf bipartit Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int NMAX = 1000;
const int MMAX = 40000;
int l[NMAX + 5] , r[MMAX + 5] , k;
bool viz[NMAX + 5];
vector <int> G[NMAX + 5];
int path(int u)
{
    if(viz[u])
        return 0;
    viz[u] = 1;
    for(int j = 0 ; j < G[u].size() ; j ++)
    {
        int v = G[u][j];
        if(!r[v] || path(r[v]))
        {
            l[u] ++;
            l[r[v]] --;
            r[v] = u;
            return 1;
        }
    }
    return 0;
}
int main()
{
    freopen("negot.in" , "r" , stdin);
    freopen("negot.out" , "w" , stdout);
    int n , m , t , i , j , x , cuplaj , gasit;
    scanf("%d%d%d" , &n , &m , &k);
    for(i = 1 ; i <= n ; i ++)
    {
        scanf("%d" , &t);
        for(j = 1 ; j <= t ; j ++)
        {
            scanf("%d" , &x);
            G[i].push_back(x);
        }
    }
    cuplaj = 0;
    do
    {
        gasit = 0;
        memset(viz , 0 , sizeof(viz));
        for(i = 1 ; i <= n ; i ++)
            if(l[i] < k && path(i))
            {
                gasit = 1;
                cuplaj ++;
            }
    }
    while(gasit == 1);
    printf("%d\n" , cuplaj);
    return 0;
}