《战略游戏》由会员分享，可在线阅读，更多相关《战略游戏（3页珍藏版）》请在金锄头文库上搜索。
1、【问题描述问题描述】Bob 喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。他要建立一个古城堡，城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能瞭望到所有的路。注意：某个士兵在一个结点上时，与该结点相连的所有边将都可以被瞭望到。请你编一程序，给定一树，帮 Bob 计算出他需要放置最少的士兵。 【文件输入文件输入】输入文件中数据表示一棵树，描述如下： 第一行 N，表示树中结点的数目。 第二行至第 N+1 行，每行描述每个结点信息，依次为：该结点标号 i，k(后面有 k 条边与结点 I 相连)，接下来 k 个数，分别是每条边的另一个
2、结点标号 r1，r2，.，rk。对于一个 n(0 #include using namespace std; ifstream fin(“bob.in“); ofstream fout(“bob.out“); int n; vector poi2000; int c,f15022; vector cen1502; bool visit15022; int dfs(int ,int); int main() finn;for (int i=1;ipk;for (int j=1;jb;poip.push_back(b);foutmin(dfs(0,1),dfs(0,0)endl; int dfs(int x1,int h1) int x=x1,h=h1;int tmp=0;if (visitxh) return fxh;visitxh=1;if (poix.size()=0) return fxh=h;if (!h)for (int i=0;ipoix.size();i+) fxh+=dfs(poixi,1);elsefor (int i=0;ipoix.size();i+) tmp+=min(dfs(poixi,0),dfs(poixi,1);fxh=tmp+1; return fxh;
