2013
11-28

# Strategic Game

Bob enjoys playing computer games, especially strategic games, but sometimes he cannot find the solution fast enough and then he is very sad. Now he has the following problem. He must defend a medieval city, the roads of which form a tree. He has to put the minimum number of soldiers on the nodes so that they can observe all the edges. Can you help him?

Your program should find the minimum number of soldiers that Bob has to put for a given tree.

The input file contains several data sets in text format. Each data set represents a tree with the following description:

the number of nodes
the description of each node in the following format
or
node_identifier:(0)

The node identifiers are integer numbers between 0 and n-1, for n nodes (0 < n <= 1500). Every edge appears only once in the input data.

For example for the tree:

the solution is one soldier ( at the node 1).

The output should be printed on the standard output. For each given input data set, print one integer number in a single line that gives the result (the minimum number of soldiers). An example is given in the following table:

4
0:(1) 1
1:(2) 2 3
2:(0)
3:(0)
5
3:(3) 1 4 2
1:(1) 0
2:(0)
0:(0)
4:(0)

1
2

/*
【题意】 给定一棵树，标记一节点，则与该节点所连的边都被标记，问最少需要标记多少个节点使得所有边都被标记；
或者说给定一个树型城堡，在交叉路口放一个士兵，则与该路口相连的路都被守住，
问最少需要派遣多少个士兵来守住这个城堡

dp[father].yes= （ min(dp[child].yes,dp[child].no) 之和）
dp[father].yes=（ min(dp[child].yes,dp[child].no) 之和）

*/
#include<stdio.h>
#include<string.h>

struct node
{
int father,brother,child;
int yes,no;

void init()
{
father=brother=child=0;
yes=1;
no=0;
}
}t[1505];

bool use[1505];
int min(int x,int y)
{
if(x<y) return x;
return y;
}

void dfs(int root)
{
int child=t[root].child;
while(child)
{
dfs(child);
t[root].yes+=min(t[child].yes,t[child].no);
t[root].no+=t[child].yes;
child=t[child].brother;
}
}
/*
void dfs(int root)
{
int child=t[root].child;
while(child)
{
dfs(child);
printf("root%d %d",root,child);
child=t[child].brother;
}
}*/

int  main()
{
int n,Root,root,cnt,j;
while(scanf("%d",&n)!=EOF)
{
memset(use,0,sizeof(use));

//int Root;

for(int i=1;i<=n;i++)
{
scanf("%d:(%d)",&root,&cnt),root++;
if(i==1) Root=root;

if(!use[root])
{
t[root].init();
use[root]=1;
}

while(cnt--)
{
scanf("%d",&j),j++;
if(!use[j])
{
t[j].init();
use[j]=1;
}
t[j].brother=t[root].child;
t[j].father=root;
t[root].child=j;
}
}

dfs(Root);

printf("%d\n",min(t[Root].no,t[Root].yes));

}

return 0;
}

1. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。

2. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。