2594.txt

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

Problem Id:2594  User Id:fzk 
#include <stdio.h>
#include <memory.h>
#include <vector>
using namespace std;
#define null 0
const int size=510;
bool w[size][size]; 
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;

}
vector< int > e[500];
bool sign[500];
void find( int s, int r )
{
	int i, t;
	sign[s] = 1;
	if( s != r ) w[r][s] = 1;

	for( i=0; i<e[s].size(); i++ )
		if( !sign[ t=e[s][i] ] )
			find( t, r );

}
int main()
{
	int n, m, i, j, a, b, ans, k;
	while( scanf( "%d %d", &n, &m ) == 2 )
	{
		if( n == 0 && m == 0 ) break;
		memset( w, 0, sizeof( w ) );
		for( i=0; i<n; i++ )
			e[i].clear();
		for( i=0; i<m; i++ )
		{
			scanf( "%d %d", &a, &b );
			w[a-1][b-1] = 1;
			e[a-1].push_back( b-1 );
		}
		for( k=0; k<n; k++ )
		{
			memset( sign, 0, n );
			find( k, k );
		}
		ans = n - maxmatch( n, n, w, 0 );
		printf( "%d\n", ans );

	}

	return 0;
}