http://poj.org/problem?id=3659
題意: 給出一棵樹(無向圖),讓你在上面選點放塔, 塔覆蓋范圍為當前點和相鄰的點,用最小的塔覆蓋所有點
解法1：樹型DP
dp[ i ][ 0 ], 表示該點不放塔, 且被祖先結點覆蓋
dp[ i ][ 1 ], 表示該點不放塔, 不被祖先覆蓋
dp[ i ][ 2 ], 放塔
u為i 的子結點dp[ i ][ 0 ] = sum( min( dp[ u ][ 1 ], dp[ u ][ 2 ] ) );
dp[ i ][ 2 ] = sum( min( dp[ u ][ 0 ], dp[ u ][ 2 ] ) ) + 1;
dp[ i ][ 1 ] 如果其子節點中至少有一個點是放塔, 即存在 dp[ u ][ 2 ] <= dp[ u ][ 1 ]
那么 dp[ i ][ 1 ] = sum( min( dp[ u ][ 1 ], dp[ u ][ 2 ] ) );
否則 枚舉其中一個子結點, 在該結點放塔( dp[ u ][ 2 ] ),其他仍保持dp[ u ][ 1 ]狀態
1 #include <cstdio>
2#include <complex>
3#include <cstdlib>
4#include <iostream>
5#include <cstring>
6#include <string>
7#include <algorithm>
8#include <cmath>
9#include <ctime>
10#include <vector>
11#include <map>
12#include <queue>
13using namespace std;
14
15const int maxn = 10004;
16const int inf = 10000000;
17
18int vis[ maxn ], id[ maxn ], f[ maxn ], set[ maxn ];
19int head[ maxn ], e[ maxn << 1 ], next[ maxn << 1 ];
20int len;
21int dp[ maxn ][ 3 ];
22
23void init( )
24   {
25 len = 0;
26 memset( head, 0, sizeof( head ) );
27 }
28
29void add( int u, int v )
30{
31 next[ ++len ] = head[ u ];
32 head[ u ] = len;
33 e[ len ] = v;
34}
35
36int Min( int a, int b ) { return ( a < b ? a : b ); }
37
38void DFS( int u )
39{
40 vis[ u ] = 1;
41 if( head[ u ] == 0 )
42  {
43 dp[ u ][ 0 ] = 0;
44 dp[ u ][ 1 ] = inf;
45 dp[ u ][ 2 ] = 1;
46 return;
47 }
48 int sum[ 3 ] = { 0 }, off = inf;
49 for( int i = head[ u ]; i ; i = next[ i ] )
50 {
51 int v = e[ i ];
52 if( !vis[ v ] )
53 {
54 DFS( v );
55 sum[ 0 ] += Min( dp[ v ][ 1 ], dp[ v ][ 2 ] );
56 sum[ 2 ] += Min( dp[ v ][ 0 ], dp[ v ][ 2 ] );
57 off = Min( off, dp[ v ][ 2 ] - dp[ v ][ 1 ] );
58 // 最后off <= 0 則存在 dp[ v ][ 2 ] <= dp[ v ][ 1 ]
59 }
60 }
61 dp[ u ][ 0 ] = sum[ 0 ];
62 dp[ u ][ 1 ] = sum[ 0 ];
63 dp[ u ][ 2 ] = sum[ 2 ] + 1;
64 if( off > 0 ) dp[ u ][ 1 ] = sum[ 0 ] + off;
65}
66
67int main(int argc, char *argv[])
68{
69 int u, v, n;
70 scanf( "%d", &n );
71 init( );
72 for( int i = 1; i < n; i++ )
73 {
74 scanf( "%d%d", &u, &v );
75 add( u, v );
76 add( v, u );
77 }
78 DFS( 1 );
79 printf( "%d\n", Min( dp[ 1 ][ 1 ], dp[ 1 ][ 2 ] ) );
80 return 0;
81}
82
解法2：貪心
先前序遍歷一次對結點進行標志,然后從n到1進行O(n)貪心.
每次選取還沒覆蓋的點,在該點的父親結點放塔.
1#include <cstdio>
2#include <complex>
3#include <cstdlib>
4#include <iostream>
5#include <cstring>
6#include <string>
7#include <algorithm>
8#include <cmath>
9#include <ctime>
10#include <vector>
11#include <map>
12#include <queue>
13using namespace std;
14
15const int maxn = 10004;
16int vis[ maxn ], id[ maxn ], f[ maxn ], set[ maxn ];
17int head[ maxn ], e[ maxn << 1 ], next[ maxn << 1 ];
18int len;
19
20void init( )
21{
22 len = 0;
23 memset( head, 0, sizeof( head ) );
24}
25
26void add( int u, int v )
27{
28 next[ ++len ] = head[ u ];
29 head[ u ] = len;
30 e[ len ] = v;
31}
32
33int num;
34
35void DFS( int u )
36{
37 vis[ u ] = 1;
38 id[ u ] = num++;
39 for( int i = head[ u ]; i ; i = next[ i ] )
40 {
41 int v = e[ i ];
42 if( !vis[ v ] )
43 {
44 DFS( v );
45 f[ id[ v ] ] = id[ u ];
46 }
47 }
48}
49
50int main(int argc, char *argv[])
51{
52 int u, v, n;
53 scanf( "%d", &n );
54 init( );
55 for( int i = 1; i < n; i++ )
56 {
57 scanf( "%d%d", &u, &v );
58 add( u, v );
59 add( v, u );
60 }
61 num = 1;
62 memset( f, 0, sizeof( f ) );
63 memset( vis, 0, sizeof( vis ) );
64 DFS( 1 );
65 memset( set, 0, sizeof( set ) );
66 memset( vis, 0, sizeof( vis ) );
67
68 int ans = 0;
69 for( int i = n; i>= 1; i-- )
70 {
71 if( !vis[ i ] )
72 {
73 if( !set[ f[ i ] ] )
74 {
75 ans++;
76 set[ f[ i ] ] = 1;
77 }
78 vis[ i ] = 1;
79 vis[ f[ i ] ] = 1;
80 vis[ f[ f[ i ] ] ] = 1;
81 }
82 }
83
84 printf( "%d\n", ans );
85 return 0;
86}
87
|