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

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;

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)

{

break;

}
}
}
if(j<m)break;
}
if(t<s)
{
{

}

}
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;
}
```
This entry was posted in poj. Bookmark the permalink.