题目:给你一棵树。找到最小的顶点集合,使得全部的边至少有一个顶点在这个集合中。
分析:树形dp,图论,最小顶点覆盖。
方案1:树形dp。分别记录每一个节点取和不取的最优解f(k。0)与f(k,1);
每一个节点的状态取决于子树,子树的根都不选,则他必选;否则取最小;
f(k。0)= sum(f(i,1))。
f(k。1)= sum(min(f(i,0)。f(i。1))){ 当中 i 是k的子树根节点 };
方案2:最小顶点覆盖 = N - 最大独立点 = 最大匹配。
说明:(2011-09-19 09:46)。
#include <stdio.h> #include <stdlib.h> #include <string.h> #define min(x,y) ((x)<(y)?(x):(y)) typedef struct node { int Count; int Value; int Next[ 10 ]; }node; node Node[ 1510 ]; int Root; typedef struct answ { int sum0; int sum1; }Answ; Answ Save; Answ dp( int Root ) { Answ an; an.sum0 = 0; an.sum1 = 1; if ( Node[ Root ].Count ) { for ( int i = 0 ; i < Node[ Root ].Count ; ++ i ) { Save = dp( Node[ Root ].Next[ i ] ); an.sum0 += Save.sum1; an.sum1 += min( Save.sum0, Save.sum1 ); } } return an; } int main() { int n,a,m,b; while ( scanf("%d",&n) != EOF ) { Root = -1; memset( Node, 0, sizeof( Node ) ); for ( int i = 0 ; i < n ; ++ i ) { scanf("%d:(%d)",&a,&m); if ( Root == -1 ) Root = a; Node[ a ].Count = m; Node[ a ].Value = a; for ( int j = 0 ; j < m ; ++ j ) { scanf("%d",&b); Node[ a ].Next[ j ] = b; } } Answ answer = dp( Root ); printf("%d ",min( answer.sum0, answer.sum1 )); } return 0; }图论解法:
#include <stdio.h> #include <stdlib.h> typedef struct node { int Point; node* Next; }node; node Node[ 3001 ]; node *Head[ 1501 ]; bool Used[ 1501 ]; int Result[ 1501 ]; bool find( int a, int n ) { for ( node *P = Head[ a ] ; P ; P = P->Next ) if ( !Used[ P->Point ] ) { Used[ P->Point ] = true; if ( Result[ P->Point ] == -1 || find( Result[ P->Point ] , n ) ) { Result[ P->Point ] = a; return true; } } return false; } int argument( int n ) { for ( int i = 0 ; i < n ; ++ i ) Result[ i ] = -1; int Count = 0; for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) Used[ j ] = false; if ( find( i, n ) ) ++ Count; } return Count; } int main() { int n,a,m,b; while ( scanf("%d",&n) != EOF ) { for ( int i = 0 ; i < n ; ++ i ) Head[ i ] = NULL; int Count = 0; for ( int i = 0 ; i < n ; ++ i ) { scanf("%d:(%d)",&a,&m); for ( int j = 0 ; j < m ; ++ j ) { scanf("%d",&b); Node[ Count ].Next = Head[ a ]; Node[ Count ].Point = b; Head[ a ] = &Node[ Count ++ ]; Node[ Count ].Next = Head[ b ]; Node[ Count ].Point = a; Head[ b ] = &Node[ Count ++ ]; } } printf("%d ",argument( n )/2); } return 0; }