Poj Solution 2594

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

#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( "%dn", ans );

    }

    return 0;
}


											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *