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