Cod sursa(job #552907)

Utilizator LgregL Greg Lgreg Data 13 martie 2011 10:20:34
Problema Cuplaj maxim in graf bipartit Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int N,M,K;
int v[250],x,p=0;
char car;
vector <int> g[250];
int l[250],r[250],u[250],was[250],S;
int cupj(int q)
{
    if(was[q])
        return 0;
    was[q]=1;
    for(int i=0;i<g[q].size();++i)
    {
        if(!r[g[q][i]])
        {

            l[q]=g[q][i];
            r[g[q][i]]=q;
            return 1;
        }
    }
    for(int i=0;i<g[q].size();++i)
    {
        if(cupj(r[g[q][i]]))
        {
            l[q]=g[q][i];
            r[g[q][i]]=q;
            return 1;
        }
    }
    return 0;


}


int main()
{
freopen("universitate.in","r",stdin);
    scanf("%d%d%d\n",&N,&M,&K);
    for(int i=1;i<=N;++i)
    {
    int ok=1;
    while(ok)
        {
        if(scanf("%d",&x)!=1)
        ok=0;
        v[i]^=1<<x;
        scanf("%c",&car);
        if(car=='\n')
            ok=0;
        }
    }

   for(int i=1;i<=M;++i)
   {
       int ok=1;
       p=0;
       while(ok)
        {
        if(scanf("%d",&x)!=1)
        {
       // printf("!");
        ok=0;
        }
        if(!(p&(1<<x)))
        p^=1<<x;
        scanf("%c",&car);
        if(car=='\n')
            ok=0;
        }
       // printf("%d\n",p);
        for(int j=1;j<=N;++j)
        {
            if(v[j]&p)
                g[i].push_back(j+N);
        }
   }
  /* for(int i=1;i<=M;++i)
   {
       for(int j=0;j<g[i].size();++j)
        printf("%d ",g[i][j]);
    printf("\n");
   }*/
   int ok=1;
   while(ok)
   {
    ok=0;
    for(int i=0;i<=M;++i)
        was[i]=0;
    for(int i=1;i<=M;++i)
        if(!l[i])
        {
            ok|= cupj(i);
        }
   }
   for(int i=1;i<=M;++i)
    if(l[i]>0)
        ++S;
    printf("%d\n",S);
  /*  for(int i=1;i<=M;++i)
        if(l[i]>0)
        {
            printf("%d %d\n",i,l[i]);
        }*/


}