1274.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <stdio.h>

#define null 0

const int size=210;

 

 

int maxmatch(int n,int m,bool w[][size],int *p)

{

       int p_n[size];

       int p_m[size];

       bool sign[size];

       int q[size],from[size],s,t;

 

       int i,j,link,now,h;

       

 

       for(i=0;i<n;i++)p_n[i]=-1;

       for(j=0;j<m;j++)p_m[j]=-1;

 

       for(i=0;i<n;i++)

       if(p_n[i]==-1)

       {

              for(j=0;j<m;j++)sign[j]=0;

                            

              s=1;link=-1;

 

              from[0]=-1;

              q[0]=size-1;

              p_m[size-1]=i;

              

              for(t=0;t<s;t++)

              {

                     now=q[t];

                     for(j=0;j<m;j++)

                     {

                            if(w[p_m[now]][j]!=null&&sign[j]==0)

                            {

                                   sign[j]=1;

                                   q[s]=j;

                                   from[s++]=t;

                                   

                                   if(p_m[j]==-1)

                                   {

                                          link=s-1;

                                          break;

                                   }

                            }

                     }

                     

                     if(j<m)break;

              }

 

              if(t<s)

              {

                     while(from[link]!=-1)

                     {

                            h=from[link];

                            p_m[q[link]]=p_m[q[h]];

                            

                            p_n[p_m[q[h]]]=q[link];

                            link=h;

                     }

 

              }

       

       }

 

       int an;

       for(i=0,an=0;i<n;i++)

       {

              if(p)p[i]=p_n[i];

              if(p_n[i]>=0)an++;

       }

       

       return an;

}

bool e[size][size];

int main()
{
	int n, m, i, j, s;
	while( scanf( "%d%d", &n, &m ) == 2 )
	{

		for( i=0; i<n; i++ )
		for( j=0; j<m; j++ )
			e[i][j] = false;

		for( i=0; i<n; i++ )
		{
			scanf( "%d", &s );
			while( s-- )
			{
				scanf( "%d", &j );
				e[i][j-1] = true;
			}
		}

		printf( "%d\n", maxmatch( n, m, e, 0 ) );
	}
	return 0;
}