Poj Solution 1463

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

#include <stdio.h>
#include <memory.h>
#define min(a,b) ((a)<(b)?(a):(b))
int e[2000][20];
int en[2000];
int ans[2000][2], n;

void calc( int k, int f ) {
    int i;
    ans[k][0] = 0, ans[k][1] = 1;
    for( i=0; i<en[k]; i++ ) {
        if( e[k][i] != f ) {
            calc( e[k][i], k );
            ans[k][0] += ans[ e[k][i] ][1];
            ans[k][1] += min( ans[ e[k][i] ][0], ans[ e[k][i] ][1] );
        }
    }
}

int main( ) {
    int i, k, m, l, j;
    while( scanf( "%d", &n ) == 1 ) {

        memset( en, 0, sizeof en );

        for( j=0; j<n; j++ ) {
            scanf( "%d:(%d)", &k, &m );
            for( i=0; i<m; i++ ) {
                scanf( "%d", &l );
                e[k][ en[k]++ ] = l;
                e[l][ en[l]++ ] = k;
            }
        }

        calc( 0, -1 );
        printf( "%dn", min( ans[0][0], ans[0][1] ) );
    }
    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 *