2672.txt

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

Problem Id:2672  User Id:fzk 
Memory:320K  Time:139MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <string.h>
#include <memory.h>


//求二分图最大匹配，

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

#define null 0

const int size=30;

 

 

bool 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;

                     } 

              }
				else return false;
       }

	return true;
       
}
bool e[10010][26];
bool w[26][30];
int sib[10010], child[10010];
int m;
char word[100];
void creat( int root )
{
	int c = -1;
	char *p;
	while( 1 )
	{
		gets( word );
		if( word[0] == '>' )
			return;
		if( word[0] == '<' )
			creat( c );
		else
		{
			if( c != -1 )
				sib[c] = m;
			else child[root] = m;
			
			sib[m] = -1;
			child[m] = -1;
			c = m;

			memset( e[m], 0, sizeof(bool)*26 );

			for( p = strtok( word, " \n\t" ); p; p = strtok( NULL, " \n\t" ) )
				e[m][ *p-'A' ] = true;
			m++;
		}
	}
}
bool search( int root )
{
	int i, j, k, n, c;
	bool key;
	for( i=0, c = child[root]; c != -1 && i < 26; c = sib[c], i++ )
		if( !search( c ) )return false;	
	if( i >= 26 )
		return false;
	if( i == 0 )
		return true;
	for( i=0, c = child[root]; c != -1 && i < 26; c = sib[c], i++ )
		for( j=0; j<26; j++ )
			w[i][j] = e[c][j];
	n = i;
	for( j=0; j<26; j++ )
		w[n][j] = 0;

	key = false;
	for( k=0; k<26; k++ )
	{
		if( e[root][k] )
		{
			w[n][k] = 1;
			e[root][k] = maxmatch( n+1, 26, w, 0 );
			if( e[root][k] )
				key = true;
			w[n][k] = 0;
		}
	}
	return key;
}
int main( )
{
	int i, c, j;
	
	child[ 0 ] = -1;
	gets( word );	
	m = 1;
	creat( 0 );
	for( i=0, c = child[0]; c!=-1; c = sib[c], i++ )
	{
		if( !search( c ) )
			break;
		for( j=0; j<26; j++ )
			w[i][j] = e[c][j];
	}
	if( c != -1 || i > 26 || !maxmatch( i, 26, w, 0 ) )
		printf( "No Solution\n" );
	else
		printf( "Got It!\n" );
	return 0;
}