Poj Solution 2672

http://poj.org/problem?id=2672

#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, " nt" ); p; p = strtok( NULL, " nt" ) )
                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 Solutionn" );
    else
        printf( "Got It!n" );
    return 0;
}