1325.txt

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

#include "stdio.h"

#define null 0

const int size=100;

 

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[100][100];

int main()
{
	int i, j, n, m, k, a, b, ans;

	while( scanf( "%d %d %d", &n, &m, &k ) == 3 )
	{
		for( i=0; i<n; i++ )
		for( j=0; j<m; j++ )
		e[i][j] = false;

		for( i=0; i<k; i++ )
		{
			scanf( "%*d %d %d", &a, &b );
			a--,b--;
			if( a >= 0 && b >= 0 )
			e[a][b] = true;
		}

		ans = maxmatch( n, m, e, 0 );

		printf( "%d\n", ans );

	}

	return 0;
}