1466.txt

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

#include <stdio.h>

//求二分图最大匹配，

//返回匹配边数，w为n*m邻接矩阵,p返回与X( |X|=n )匹配的顶点编号

#define null 0

const int size=500;

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 w[500][500];
int n;

int id[500], boys, girls;
int e[500][500];
bool sign[500];

void find( int a ,bool boy )
{
	sign[a] = true;

	if( boy ) id[a] = boys++;
	else id[a] = -(girls++);

	for(int i=0; i<n; i++ )
	if( !sign[i] && e[a][i] )
	{
		find( i, !boy );
	}
}

bool init()
{
	int i, j, a, b, c;
	
	if( scanf( "%d", &n ) != 1 ) return false;

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

	for( i=0; i<n; i++ )
	{
		scanf( "%d: (%d)", &a, &c );

		while( c-- )
		{
			scanf("%d", &b );
			e[a][b] = true;
		}
	}

	boys = 0;
	girls = 1;

	for( i=0; i<n; i++ )
		sign[i] = false;

	for( i=0; i<n; i++ )
	if( !sign[i] )
	{
		find( i, true );
	}

	for( i=0; i<n; i++ )
	if( id[i] >= 0 )
	{
		for( j=0; j<n; j++ )
		if( e[i][j] )
		{
			w[id[i]][-id[j]-1] = true;
		}
	}
	girls -- ;

	return true;
}

int main()
{
	int ans;

	while( init() )
	{
		ans = maxmatch( boys, girls, w, 0 );
		printf( "%d\n", n-ans );
	}

	return 0;
}