POJ 1463 Strategic game( 树形DP )
来源：程序员人生 发布时间：2014-09-29 13:26:30 阅读次数：3054次
题意：一颗 N 个节点的树，在某一个节点上放置一个兵则可以守住与它相邻的边。最少放置多少个兵才可以守住所有的边。
#include <cstdio>
#include <deque>
using namespace std;
#define ABANDON 0
#define GET 1
deque< int > graph[2010];
int DP[2010][2];
void DFS( int start, int parent ){
DP[start][ABANDON] = 0;
DP[start][GET] = 1;
int target;
if( graph[start].size() == 1 && parent != -1 )
return;
for( int i = 0; i < graph[start].size(); ++i ){
target = graph[start][i];
if( target == parent )
continue;
DFS( target, start );
DP[start][ABANDON] += DP[target][GET];
DP[start][GET] += min( DP[target][GET], DP[target][ABANDON] );
}
}
int main(){
int nodes;
int start, roads, target;
while( scanf( "%d", &nodes ) != EOF ){
for( int i = 0; i <= nodes; ++i )
graph[i].clear();
for( int i = 0; i < nodes; ++i ){
scanf( "%d:(%d)", &start, &roads );
while( roads-- ){
scanf( "%d", &target );
graph[start].push_back( target );
graph[target].push_back( start );
}
}
DFS( 0, -1 );
printf( "%d
", min( DP[0][ABANDON], DP[0][GET] ) );
}
return 0;
}</span>
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
